Svejedno je, ako se koristi adekvatan ključ, nijedan od tih algoritama neće biti dovoljno brz.

Već postoje implementacije za post-quantum algoritme, od 6 u opciji mislim da su 3 već odobrena od strane NIST-a, ali su na njima radili nezavisni istraživači sa univerziteta i instituta, tako da se nadamo da neće biti problema kao sa eliptičkim krivim gde se sumnja da je NSA preko NIST-a ubacila "backdoor" kroz preporučene eliptičke krive (radi se o standardu NIST FIPS 186-3).

Za Šorov algoritam se pre neku godinu, kad sam zadnji put čitao nešto o tome, smatralo da bi bio potreban računar reda nekoliko miliona kubita, mislim da je išlo i do 20 miliona, ali navodno se algoritam usavršava i smanjuje se broj potrebnih kubita, međutim realna implementacija je daleko u budućnosti i ima smisla samo za podatke koji i tada u budućnosti budu imali značaj ako se se sada sačuvaju enkriptovani. Za ogromnu većinu podataka to nije slučaj, osim onih iz domena određenih vojnih i civilnih službi, tako da za "obične" građana nema problema.

Ovo je tacno ako se radi o nekom random kljucu... Medjutim postoje Puzzle kljucevi koji su jasno definisani...

npr puzzle 135 140 145 150 155 i 160
Svi ovi kljucevi se zapravo nalaze izmedju opsega od 2^(broj puzzle - 1) do 2^(broj puzzle)

2^134 i 2^135 je puzzla 135 medjutim ako je bilo kakav najbrzi algoritam koren iz N onda dodlazimo do toga da treba izvrsiti 2^62 (otprilike iteracija) sto je oko 4 milijarde milijardi sto je onako dosta tesko za bilo koji racunar

Address: 16RGFo6hjq9ym6Pj7N5H7L1NR1rVPJyw2v
Range Hex: 4000000000000000000000000000000000 to 7fffffffffffffffffffffffffffffffff
Start Key: 0000000000000000000000000000004000000000000000000000000000000000
Stop Key: 0000000000000000000000000000007fffffffffffffffffffffffffffffffff

Prebaci u forum programiranje.
Možda ti neko pomogne.

Postoji brži algoritam za razbijanje RSA na primer i to se uzima u obzir pri izboru veličine ključa.

Međutim, ja ne znam za kripto algoritam javnim ključem kod koga ključevi komutiraju (primena istih ključeva u bio kom redosledu daje isti rezultat), a da je postkvantni. To ima primene.

Sad iz naslova vidim da nije tema RSA, nego eliptičke krive.

Što se tiče RSA i srodnih algoritama, oni se odnose na konačne komutativne prstene. Računanje u prstenu je računanje u dekadnom sistemu uz odbacivanje svih cifara osim poslednje. Kod RSA imamo računanje po modulu n (umesto 10), gde je n proizvod neka dva nepoznata velika prosta broja.

Tu se uvodi algebarski izvod polinoma. Za je . Za njega se dokazuje većina osobina na koje smo navikli u diferencijanom računu. To se zove diferencijalna analiza na prstenima (i poljima). Ona je primenljiva na efikasniju kriptoanalizu. Metodama diferencijalne analize u diskretnom slučaju se mogu naći matematičke prečice za brže razbijanje, tako da su potrebni veći ključevi da bi bili bezbedni, ali onda je potrebno i više računskih operacija za normalnu primenu.

Zato su smišljeni algoritmi sa eliptičkim krivama. To su komutativne grupe, ali koje nisu prsteni, pa da se mogu definisati polinomi i diferencijalni račun, tako da te matematičke prečice ne postoje, pa su manji ključevi dovoljni da bi bili sigurni, a onda je i normalna primena efikasnija..

Postoji i drugi način, ne znam koliko zahteva prostora, ali postoje algoritmi kojima se može odrediti da li je neki broj prost bez obimnih izračunavanja, ako se zna koliko delilaca imaju prethodna 2 broja. Jedini problem je što počevši od nekog velikog broja treba odrediti broj delilaca za sve prirodne brojeve do nekog ili tako nešto. Recimo, ako neko napravi tabelu prostih brojeva koji imaju 1024 do 2048 bita, možda može da razbije svaku RSA enkripciju pod uslovom da p iili q ima najmanje 1024 bita.
Za "storage" takođe nije problem, jer bi se pamtili samo prosti brojevi, tj. ne mora da se pamti broj delilaca za sve brojeve, to je važno samo za ispitivanje narednog broja za koji se ne zna broj delilaca.

Onda bi se razbijanje RSA enkripcije svelo na pretraživanje "malo veće" tabele.

Pa, tolikih prostih brojeva ima oko 1.3*10⁶⁰³.

Kako radi taj algoritam?

Mozda postoji brzi algoritam za faktorizaciju brojeva ali mislim da ne postoji brzi nacin da se resi opseg od secp256k1... Jednostavno ne postoji nikakva podgrupa ili deo krive koji je specifican po necemu pa da se kaze - e ovde se do resenja dodje brze... I jos jedna stvar - kod krive nista nije random... U smilu ravnomerno je popunjen prostor tackama koje imaju odredjene osobine...

Na primer

Ako trazite tacku kod koje se hexadecimalna vrednost X ose zavrsava sa "0000" ili "1234" ili "ffff" i ako skenirate +1G+1G+1G+1G+1G.... pronalazicete nekad pre nekad kasnije ove tacke ali u svakom slucaju tezicete ka tome da imate neki prosek od svakih 65.000 "skokova" (iteracija)

E sad ako ne skenirate +1G nego skenirate +(1x10^40ti)G i tako dodajete +(1x10^40ti)G +(1x10^40ti)G +(1x10^40ti)G +(1x10^40ti)G +(1x10^40ti)G OPET cete pronalaziti nekad pre nekad kasnije ove tacke ali u svakom slucaju tezicete ka tome da imate neki prosek od svakih 65.000 "skokova" (iteracija)

Znaci nesto tu ima posto nije random... Nekako se nesto moze zakljuciti - ali za sad koren iz N je najbolje resenje...

A da počneš od [sqrt(N) + 1] ^ 2 pa nizbrdo, mslm na dole .. ?

Samo bi mnogo sporije radilo.

Puno više ima kandidata od [sqrt(N) + 1] ^ 2 do [N/2 + 1] nego od 2 do [sqrt(N) + 1].

Prvo napravite tabelu prostih brojeva od 3.3*10⁶⁰⁵ bajtova.

Ali je nekako predvidljivo .. nXn = n^2, (n-1)x(n+1) = (n^2) - 1 .. (n-2)x(n+2) = (n^2) - 3 ... Itd.. korak je 2, brzo dođeš u blizinu ciljanog broja ...

Mislim da je o tome pisao Ojler, jedan naš profesor je pisao par radova na temu "Sum of divisors", pominje se i ovde u nekim komentarima: https://math.stackexchange.com...ll-proper-divisors-of-a-number

Pored objavljenog bar jednog rada na tu temu, mislim da je u Kragujevac Journal of Mathematics, ako se dobro sećam, taj profesor je napisao bar još jedan rad koji nije objavio, mislim da je imao neki rezultat kao što sam pomenuo u prethodnom komentaru, ali je promenio sferu interesovanja i počeo da se bavi geometrijom, tako da je taj drugi rad ostao neobjavljen.
Uglavnom, ako se posmatra samo broj "n", onda je neophodno rekurzivno računati sume delilaca sve do broja 1. Dakle, prednost algoritma je kada su do nekog broja "m" poznate sume delilaca za svaki prirodan broj, onda je određivanje te sume za svaki sledeći broj jednostavno, što nije slučaj kada se radi faktorizacija.

Na kraju neupotrebljivo za kriptoanalizu RSA.

Hvala MJaniću.
Pogledaću.

Nedeljko ne zanima me RSA.

Pa, ne znam onda šta te zanima. Broj prostih brojeva manjih od n je asimptotski ekvivalentan sa n/ln(n).

To znam.
Zanima me brži algoritam za generisanje prostih brojeva.
Ovo MJanićevo liči na to.

Praktično se koristi mala Fermaova teorema po kojoj je deljivo sa za svaki prost broj i prirodan broj koji nije deljiv sa .

Dakle, izaberimo nasumično broj sa željenim brojem binarnih cifara, izaberimo neki prirodan broj veći od jedinice, ali manji od , što znači da ne može biti deljiv sa .

Zatim se izračuna po modulu . Ako se ne dobije nula, onda broj ne može biti prost. Ako se pak dobije nula, onda je prost sa verovatnoćom koja nije manja od 0.75. Ako isti postupak primenimo na n međusobno različitih prostih brojeva i uvek dobijemo nulu, onda je broj prost sa verovatnoćom koja nijae manja od i tako se prihvata da je broj prost. Za stepenovanje se koristi sledeći algoritam stepenovanja.

Kako se računa na primer ?

,
,
,
.

Dakle, i .

Svaki put se izračuna ostatak pri delenju sa , dok se množenje vrši preko FFT da bi bilo brže.

Kada se neki broj prihvati kao prost, onda je to do na verovatnoću.

Inače je izuzetno teško naći veliki broj koji je sigurno prost.

Hvala Nedeljko.