p = 7 #prime
element = 2
value = 1
for _ in range(10):
print(value)
value = (value*element) % p
1 2 4 1 2 4 1 2 4 1
We can see, that element $2$ has period $1,2, 4$ with the length 3.
[(element**i) % p for i in range(10)] #pythonic
[1, 2, 4, 1, 2, 4, 1, 2, 4, 1]
values = [(element**i) % p for i in range(10)]
set(values)
{1, 2, 4}
len(set(values))
3
Let's have look at all elements:
for element in range(1, p):
values = [(element**i) % p for i in range(10)]
val_set = set(values)
print(element, values, val_set, len(val_set))
1 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] {1} 1 2 [1, 2, 4, 1, 2, 4, 1, 2, 4, 1] {1, 2, 4} 3 3 [1, 3, 2, 6, 4, 5, 1, 3, 2, 6] {1, 2, 3, 4, 5, 6} 6 4 [1, 4, 2, 1, 4, 2, 1, 4, 2, 1] {1, 2, 4} 3 5 [1, 5, 4, 6, 2, 3, 1, 5, 4, 6] {1, 2, 3, 4, 5, 6} 6 6 [1, 6, 1, 6, 1, 6, 1, 6, 1, 6] {1, 6} 2
Due to Fermat's Theorem it is enough to compute up to $p-1$.
$$ a^{p-1} = 1 \mod p $$for element in range(1, p):
values = [(element**i) % p for i in range(p-1)]
val_set = set(values)
print(element, values, val_set, len(val_set))
1 [1, 1, 1, 1, 1, 1] {1} 1 2 [1, 2, 4, 1, 2, 4] {1, 2, 4} 3 3 [1, 3, 2, 6, 4, 5] {1, 2, 3, 4, 5, 6} 6 4 [1, 4, 2, 1, 4, 2] {1, 2, 4} 3 5 [1, 5, 4, 6, 2, 3] {1, 2, 3, 4, 5, 6} 6 6 [1, 6, 1, 6, 1, 6] {1, 6} 2
p=17
for element in range(1, p):
values = [(element**i) % p for i in range(p-1)]
val_set = set(values)
print(element, values, val_set, len(val_set))
1 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] {1} 1 2 [1, 2, 4, 8, 16, 15, 13, 9, 1, 2, 4, 8, 16, 15, 13, 9] {1, 2, 4, 8, 9, 13, 15, 16} 8 3 [1, 3, 9, 10, 13, 5, 15, 11, 16, 14, 8, 7, 4, 12, 2, 6] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16} 16 4 [1, 4, 16, 13, 1, 4, 16, 13, 1, 4, 16, 13, 1, 4, 16, 13] {16, 1, 4, 13} 4 5 [1, 5, 8, 6, 13, 14, 2, 10, 16, 12, 9, 11, 4, 3, 15, 7] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16} 16 6 [1, 6, 2, 12, 4, 7, 8, 14, 16, 11, 15, 5, 13, 10, 9, 3] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16} 16 7 [1, 7, 15, 3, 4, 11, 9, 12, 16, 10, 2, 14, 13, 6, 8, 5] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16} 16 8 [1, 8, 13, 2, 16, 9, 4, 15, 1, 8, 13, 2, 16, 9, 4, 15] {1, 2, 4, 8, 9, 13, 15, 16} 8 9 [1, 9, 13, 15, 16, 8, 4, 2, 1, 9, 13, 15, 16, 8, 4, 2] {1, 2, 4, 8, 9, 13, 15, 16} 8 10 [1, 10, 15, 14, 4, 6, 9, 5, 16, 7, 2, 3, 13, 11, 8, 12] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16} 16 11 [1, 11, 2, 5, 4, 10, 8, 3, 16, 6, 15, 12, 13, 7, 9, 14] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16} 16 12 [1, 12, 8, 11, 13, 3, 2, 7, 16, 5, 9, 6, 4, 14, 15, 10] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16} 16 13 [1, 13, 16, 4, 1, 13, 16, 4, 1, 13, 16, 4, 1, 13, 16, 4] {16, 1, 4, 13} 4 14 [1, 14, 9, 7, 13, 12, 15, 6, 16, 3, 8, 10, 4, 5, 2, 11] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16} 16 15 [1, 15, 4, 9, 16, 2, 13, 8, 1, 15, 4, 9, 16, 2, 13, 8] {1, 2, 4, 8, 9, 13, 15, 16} 8 16 [1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16, 1, 16] {16, 1} 2
element which generates whole group, i.e. it's subgroup is $Z^*_p$.
p = 7
for element in range(1, p):
if len(set((element**i) % p for i in range(p-1))) == p-1:
print(element)
3 5
There are two generators of $Z^*_7$.
How we can find big prime?
How we can check if the number is prime?
... check up to n-1 if they are coprime
... check up to n//2 if they are coprime
... check up to sqrt(n) if they are coprime
from sympy import nextprime
p = nextprime(1000)
p
1009
%%time #only in Jupyter Notebook
count = 0
for element in range(1, p):
if len(set((element**i) % p for i in range(p-1))) == p-1:
print(element, end=" ")
count +=1
print()
print(f'# generators: {count}')
11 17 22 26 31 33 34 38 46 51 52 53 55 65 66 76 78 79 83 85 86 88 89 91 92 94 95 97 99 102 106 107 114 115 118 124 130 133 138 146 153 154 156 158 159 161 163 165 166 172 176 178 181 188 190 193 194 195 198 208 214 215 220 228 233 234 235 237 238 239 244 248 249 257 258 262 263 264 265 267 272 273 277 279 281 282 285 291 293 297 298 301 304 305 307 308 310 311 318 319 321 325 326 329 340 342 358 364 366 367 368 372 377 385 389 390 395 399 401 408 413 415 416 419 422 424 430 434 439 445 446 458 462 466 468 470 474 475 477 483 489 493 495 498 511 514 516 520 526 532 534 535 539 541 543 547 551 563 564 570 575 579 585 587 590 593 594 596 601 608 610 614 619 620 624 632 637 641 642 643 645 651 667 669 680 683 684 688 690 691 698 699 701 702 704 705 708 711 712 716 718 724 727 728 730 732 736 737 742 744 745 746 747 751 752 760 761 765 770 771 772 774 775 776 781 789 794 795 801 811 814 815 816 819 821 828 831 833 837 843 844 846 848 850 851 853 855 856 863 871 876 879 885 891 894 895 902 903 907 910 912 914 915 917 918 920 921 923 924 926 930 931 933 943 944 954 956 957 958 963 971 975 976 978 983 987 992 998 # geneators: 288 CPU times: total: 5.14 s Wall time: 5.14 s
p = nextprime(2**420)
p
2707685248164858261307045101702230179137145581421695874189921465443966120903931272499975005961073806735733604454495675614232621
p.bit_length()
421
#420 bits
p = nextprime(2**419)
p
1353842624082429130653522550851115089568572790710847937094960732721983060451965636249987502980536903367866802227247837807116587
p.bit_length()
420
len(str(p))
127
Let's find a generator ...
Is 2 generator of this group?
len(set((2**i) % p for i in range(p-1))) == p-1
--------------------------------------------------------------------------- KeyboardInterrupt Traceback (most recent call last) Cell In[31], line 1 ----> 1 len(set((2**i) % p for i in range(p-1))) == p-1 Cell In[31], line 1, in <genexpr>(.0) ----> 1 len(set((2**i) % p for i in range(p-1))) == p-1 KeyboardInterrupt:
2**1000
10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376
2**1000 // 10**9 * 3600 * 24 * 365 # number of computation in years
337910954362261262334295323471562170978644621419457078443461122476473907482759855589455040743317845819118256051279560382791018137295928156789209638395694255016880529346856948356239008745246936330263163088378473635082240099808687533745844593883486256073917252120322793799339315170997162663298096880000
%%time
2**(2**30) % p
CPU times: total: 4.95 s Wall time: 4.95 s
78901941210957546066537551109797957628504922141799931996239922263070333717389381451934067863145956699568093554366826057093204
%%time
2**(2**35) % p
## Fast Power Modulo
pow(7, 10, 9) # fast computation 7**10 % 9
7
%%time
pow(2, 2**30, p)
CPU times: total: 0 ns Wall time: 0 ns
78901941210957546066537551109797957628504922141799931996239922263070333717389381451934067863145956699568093554366826057093204
#Task 2
p = 9081321110693270343633073697474256143651
Can we compute factors of $p-1$ ?
from sympy import primefactors
primefactors(p-1)
[2, 5, 127, 208799, 9178424999, 746240351985233875199]
To check if 2 is generator:
2**((p-1)//2) % p
pow(2, (p-1)//2, p)
9081321110693270343633073697474256143650
pow(2, (p-1)//5, p)
1
Therefore 2 is NOT GENERATOR
$$ ? g^{\frac{p-1}{factor}} \mod p = 1 ?$$
def is_generator(g, p, factors):
for factor in factors:
if pow(2, (p-1)//factor, p) == 1:
return 0
return 1
is_generator(2, p, [2, 5, 127, 208799, 9178424999, 746240351985233875199])
0
is_generator(7, p, [2, 5, 127, 208799, 9178424999, 746240351985233875199])
0
is_generator(123456, p, [2, 5, 127, 208799, 9178424999, 746240351985233875199])
0
len(str(10**34))
35
def find_generator(start, p, factors):
""" find the generator of the Zp >= start
...
p, q = 61, 53 #two primes
e = 17 #random integer 1 < e < phi(n)
m = 65 #plaintext message
n = p*q
n
3233
$ c = m^e \mod n$
c = m**e % n
c
2790
$ m = c^d \mod n$
$$ d \cdot e = 1 \mod \phi(n) $$from math import gcd
count = 0
n = 12
for i in range(1, n):
if gcd(i, n) == 1:
count += 1
print(count)
4
sum(1 if gcd(i,n) == 1 else 0 for i in range(1, n))
4
from sympy import totient
totient(12)
n = 3233
totient(n)
(p-1)*(q-1)
3120
%%time
tot = 3120
#let's find the inverse brute-force
for i in range(tot):
if i*e % tot == 1:
print(i)
2753 CPU times: total: 0 ns Wall time: 0 ns
from sympy import mod_inverse
mod_inverse(e, tot)
2753
pow(e, -1, tot) # Python 3.9+
2753
[x for x in b'KRS']
[75, 82, 83]
83*256*256+82*256+75
5460555
number = 5460555
number.to_bytes(length=3, byteorder='little')
b'KRS'