@SureshPatil/

Prime Numbers

Python

No description

fork
loading
Files
  • main.py
main.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
import random
import math
import time

def trial(n, d, r):
  a = random.randint(2, n-1)
  check = pow(a, d, n) - 1
  if check%n == 0:
    return True
  for s in range(0, r):
    check = pow(a, d * pow(2, s), n) + 1
    if check%n == 0:
      return True
  return False

def isPrime(p):
  if p%2 == 0:
    return False
  r = 0
  d = p - 1
  while True:
    if d % 2 != 0:
      break
    else:
      r += 1
      d = d//2
  for i in range(10):
    if trial(p, d, r) == False:
      return False
  return True

def isSquare(n):
  val = int(math.sqrt(n))
  if val * val == n:
    return True
  else:
    return False

def factor(n):
  val = int(math.sqrt(n))
  if isSquare(n):
    return [val, val]
  for x in range(val + 1, n):
    ySquare = x**2 - n
    if isSquare(ySquare):
      return [int(x - math.sqrt(ySquare)), int(x + math.sqrt(ySquare))]



def findPrime(number):
  if number % 2 == 0:
    number += 1
  while isPrime(number) == False:
    number += 2
  return number
  
def run_trial(n):
  # n = 512
  print('Between 2 to the', n - 1, 'th and 2 to the', n, 'th power')
  start = time.perf_counter()
  primes = []
  for x in range(2):
    rando = random.randint(2**(n-1) + 1, 2**n)
    primes.append(findPrime(rando))
  end = time.perf_counter()
  findPrimeTime = end - start
  print('Found Primes', primes[0], 'and', primes[1])
  product = primes[0]*primes[1]
  print('Product', product)
  start = time.perf_counter()
  factors = factor(product)
  end = time.perf_counter()
  factorTime = end - start
  print('Factored to (', factors[0], ',', factors[1], ')')
  print('Finding primes took', findPrimeTime)
  print('Finding product took', factorTime)

def run_multiple_trials(n, numTrials):
  primeFindingTimes = []
  factoringTimes = []
  print('Between 2 to the', n - 1, 'th and 2 to the', n, 'th power')
  for x in range(0, numTrials):
    start = time.perf_counter()
    primes = []
    for x in range(2):
      rando = random.randint(2**(n-1) + 1, 2**n)
      primes.append(findPrime(rando))
    end = time.perf_counter()
    findPrimeTime = end - start
    primeFindingTimes.append(findPrimeTime)
    product = primes[0]*primes[1]
    start = time.perf_counter()
    factors = factor(product)
    end = time.perf_counter()
    factorTime = end - start
    factoringTimes.append(factorTime)

  print('Average time to find two primes', sum(primeFindingTimes)/len(primeFindingTimes))
  print('Average time to factor product', sum(factoringTimes)/len(factoringTimes))    

# run_trial(26)
# run_multiple_trials(28, 10)
# end = time.perf_counter()
# print(end - start)
print(factor(2494279923802253606287472092668310204875649561581672691813431640440219048972006082731965879))