Másodlagos szermaradvány-probléma
A algoritmikus számelméleti , a probléma a kvadratikus residuality hogy megkülönböztesse, számítással, a kvadratikus maradék modulo rögzített
vegyület száma N.
Ezt a problémát számítási szempontból nehéznek tartják általános esetben, és további információk nélkül. Ennélfogva ez egy jelentős probléma a rejtjelezésben, ahol számítási hipotézisként alkalmazzák, amint azt az Alkalmazás szakasz mutatja .
Megfogalmazás
Hagy számos, amelynek tagjai a sajátos formája , ahol és két külön páratlan prímszám. A magasság négyzet alkalmazás,
NEM{\ displaystyle N}
NEM=oq{\ displaystyle N = pq}
o{\ displaystyle p}
q{\ displaystyle q}![q](https://wikimedia.org/api/rest_v1/media/math/render/svg/06809d64fa7c817ffc7e323f85997f783dbdf71d)
nál nél¯(modNEM)↦nál nél2¯(modNEM){\ displaystyle {\ overline {a}} {\ pmod {N}} \ mapsto {\ overline {a ^ {2}}} {\ pmod {N}}}![{\ displaystyle {\ overline {a}} {\ pmod {N}} \ mapsto {\ overline {a ^ {2}}} {\ pmod {N}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b117b8c5a54f3b5f4b7824e546d806c44af1c688)
egy endomorphism a csoport invertibles a gyűrű ℤ / N ℤ , és annak kernel izomorf a Klein-csoport , a rend 4. Ezért, a kép ennek a térkép egy alcsoportja a index 4, ezért a rend ( p - 1) ( q -1) / 4. Ennek az alcsoportnak tehát 2-es indexe van azoknál az elemeknél, amelyek Jacobi-szimbóluma egyenlő 1-vel. A Jacobi-szimbólum így lehetővé teszi a csoport elemeinek felének kiküszöbölését (olyanoké, amelyek szimbóluma -1, ), és továbbra is fennáll a probléma a fennmaradó fél tetszőleges elemének meghatározása szempontjából, hogy ez négyzet-e vagy sem (egy az egyben esélye van arra, hogy egy legyen).
Alkalmazás
A másodfokú residuosity probléma használunk összetettsége hipotézis különböző kriptográfiai protokollok, mint titkosítórendszer Goldwasser Micali , vagy a generátor áivéietlen a Blum Blum Shub .
Számítás N faktorizálással ismert
Ha ismert a faktorizáció , akkor a probléma számítási szempontból könnyűvé válik, köszönhetően a másodfokú kölcsönösség törvényének és a kínai fennmaradó tételnek . A következő eljárás meghatározza, hogy a modulo négyzet értéke-e .
NEM{\ displaystyle N}
x{\ displaystyle x}
NEM{\ displaystyle N}![NEM](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3)
- Számítsa ki a mod és a mod értékeket .xo: =x{\ displaystyle x_ {p}: = x}
o{\ displaystyle p}
xq: =x{\ displaystyle x_ {q}: = x}
q{\ displaystyle q}![q](https://wikimedia.org/api/rest_v1/media/math/render/svg/06809d64fa7c817ffc7e323f85997f783dbdf71d)
- Ha mod és mod , akkor modulo másodfokú maradék .xo(o-1)/2=1{\ displaystyle x_ {p} ^ {(p-1) / 2} = 1}
o{\ displaystyle p}
xq(q-1)/2=1{\ displaystyle x_ {q} ^ {(q-1) / 2} = 1}
q{\ displaystyle q}
x{\ displaystyle x}
NEM{\ displaystyle N}![NEM](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3)
Ennek eredményeként például gyors moduláris hatványozást alkalmazunk egy komplexitás algoritmushoz , amely polinom méretű a bemenet méretében (itt ).
O((naplóNEM)2){\ displaystyle {\ mathcal {O}} {\ bigl (} (\ log N) ^ {2} {\ bigr)}}
≈naplóNEM{\ displaystyle \ approx \ log N}![{\ displaystyle \ approx \ log N}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4bab3187bcf6f4fe46c6821f7a35fde499adf8da)
Megjegyzések és hivatkozások
(
fr ) Ez a cikk részben vagy egészben az
angol Wikipedia cikkéből származik, a
" Másodlagos maradékosság problémája " címmel ( lásd a szerzők felsorolását ) .
Megjegyzések
-
Helyesebb igazolás a maradékosság lenne . A neologizmus maradványait a legtöbb kriptográfus elfogadta.
Hivatkozások
-
(in) Victor Shoup , a bevezetés a számítógépes számelmélet és az algebra , Cambridge University Press ,2009, 2 nd ed. , 580 p. ( ISBN 978-0-521-51644-0 és 0521516447 , OCLC 277069279 , olvasható online ) , 12. Másodfokú kölcsönösség és moduláris négyzetgyökök kiszámítása, fejezet. 4. („A másodfokú maradékosság tesztelése”) , p. 349.
Kapcsolódó cikk
Felső maradék probléma
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">