p, g = 23, 5 #public
#Alice
a = 4 #private
A = g**a % p #public
A
4
#Bob
b = 3 #private
B = g**b % p #public
B
10
#Alice
B**a % p
18
#Bob
A**b % p
18
from sympy import nextprime, primefactors
p = nextprime(2**511)
p
6703903964971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503042159
primefactors(p-1)
[2, 7, 17, 9433, 2986076933994148269835385919048238066318085404759171355727648743353559431103560755510084456357598398009587265648506906928241789019762235105800049577]
pf_ind = [(p-1)//div for div in primefactors(p-1)]
def check(g):
for index in pf_ind:
if pow(g, index, p) == 1: #fast computation of g**index % p
return False
return True
check(5)
False
from random import randrange
g = randrange(2, p)
print(g)
check(g)
3544101288771412016671181691316618577465024575632197348958316564992119850784951691985179750485749662865967596601962448275298849448847237466683105464815087
True
from sympy import randprime
p = randprime(2**511, 2**512)
p
8904727815073295864843904532786751808015691144123443200152692672685952796141058689520290280376776294067978323008769910591548864397343971723774251659453223
%%time
primefactors(p-1)