Your cart is currently empty!
(20 pts) Consider the following modulus: n=939239898295368386454257928783918841858520900150470969283254956807 35077974573254200941142654635659889069058397106827931666572379715390977 19986173062295693497645667236532793240467126595225167687394644118349823 12322385289785140165924807414291336465904667368386284745379274841151463 06435052269979805285188280829 Consider also the following number: y=569447780950260645088033205573241948282176043580025848609939831272462 57172572625621288924208876440674553832158479040031724187898214806257072 82396616835234960661153736217701847786032842029574125560248551274952317 68758619888643277232670079591128187448318843774948004643049766898511829 57989115066715277845807162 The integer y is a quadratic residue modulus n, and its square roots are known: { 11539293044780349664317193739835099161008802876501927386196632728052884 86457071353220342763943110690181368461236858334836627848090394205820290 38970046491030557432857518959706904266096947598325119760350627655865274 04034628524567695175048634551582051994897593554954834163440853023500476 963332472457537871514030, 65462078929074573896561682473134429960343753900612807859205872292206976 67376676479563868864251525057291006528153746980252046514530119307032029 50803240249666774951224266896062048302455238692324439395393870291836518 68429281477875679397889633306037656227303018935833418527282673149878942 564121394686954099450002, …
35077974573254200941142654635659889069058397106827931666572379715390977
19986173062295693497645667236532793240467126595225167687394644118349823
12322385289785140165924807414291336465904667368386284745379274841151463
06435052269979805285188280829
Consider also the following number:
y=569447780950260645088033205573241948282176043580025848609939831272462
57172572625621288924208876440674553832158479040031724187898214806257072
82396616835234960661153736217701847786032842029574125560248551274952317
68758619888643277232670079591128187448318843774948004643049766898511829
57989115066715277845807162
The integer y is a quadratic residue modulus n, and its square roots are known:
{
11539293044780349664317193739835099161008802876501927386196632728052884
86457071353220342763943110690181368461236858334836627848090394205820290
38970046491030557432857518959706904266096947598325119760350627655865274
04034628524567695175048634551582051994897593554954834163440853023500476
963332472457537871514030,
65462078929074573896561682473134429960343753900612807859205872292206976
67376676479563868864251525057291006528153746980252046514530119307032029
50803240249666774951224266896062048302455238692324439395393870291836518
68429281477875679397889633306037656227303018935833418527282673149878942
564121394686954099450002,
28461910900462264748864110405257454225508336114434289069119623388528101
30080648940530245401212040931615899311556935812914610723441419790687956
66502989319682989615499386383261998410204283824444300069017964690475803
70099697036140913082851795827608934239433819692641119400201441996427492
488148585118331088830827,
82384696784756488981108599138556785024843287138545169542128862952682193
11000254066873771501520455298725537378473824458330029389881144891899695
78336183078319207133866134319617142446562574918443619704061207326447048
34494349989448897305692794582064538471839245073519703764043262122805958
088937507347747316766799
}
Factor n.
p=
12997110888321186459316436989724265349460712629389513072528028592113
49992754931553520927567347008982230373355213726438110126392805826019
0003283395786606613
q=
12208677561088985820124024567796306546470708824672729385334541873189
39879463365005233532430971148076391902849072776428860469422008793314
8985261608483250761
n=p×q
m=
10450838352783190882303686938664826175340681976411643293757703902133
48484538714692972539143948801213556080672371890885302410647091183100
89323613713098921642285063603825756456138538154719968501891170428872
54615084192691202705357722526411190331450509121790329499844817869229
5392732881494063202944747727969714684 e = 67
the following values: cp = c mod p, cq = c mod q, dp = d mod (p-1), dq = d mod(q-1), p-1 mod q, q-1 mod p, cpdp mod p, and cqdq mod q. (15 pts)
import timeit
import time
…
iter = 100
t1 = time.clock()
for i in range(0, iter):
pow(c, d, n)
t2 = time.clock()
print t2-t1
Which one is faster? (Warning: In exponentiation with CRT, you should not include the execution times of values that can be precomputed, such as p-1 mod q and q-1 mod p)
b = 102092299425228521972149597163 (5 pts)
a = 44575693167043501900449109190
b = 84664078284205068314514580089 (5 pts)
b = 2124884389680246530198080982220 (5 pts)
p1(x) = x6 + x + 1
p2(x) = x6 + x2 + 1
polynomials generate all nonzero elements of the field GF(26) which has 64 elements. (10 pts)
Fall 2017