: Implement an algorithm to generate prime numbers. You will need to implement t

Question

: Implement an algorithm to generate prime numbers. You will need to implement the following ingredients (some of them you developed for earlier assignments):

1. A method to generate random binary numbers with n-digits (hint: for the most significant digit, you have no choice, it will be 1; similarly, for the least significant digit there is no choice, it will have to be 1; for all other position, generate 0 or 1 at random)

2. A method to compute modular exponentiation. It will require that you also implement the algorithm for modular addition and multiplication.

3. A method to test primality. Since the numbers you will be testing are randomly generated, use the first algorithm we discussed with a single test 3^(N1) 1(mod N)

Explanation / Answer

import random

def randomBinary(n):
min = 2**(n - 1)
max = 2**n - 1
return bin(random.randrange(min, max))[2:]

def modExpo(a, b, c):
if b == 0:
return 1
result = modExpo(a, b//2, c)
result = (result * result) % c
if b % 2 == 1:
result = (result * a) % c
return result

def is_prime(N):
if modExpo(3, N - 1, N) == 1:
return True
else:
return False

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.