Generator naprawdę dużych liczb pierwszych

Odpowiedz Nowy wątek
2019-09-04 09:33
0

Potrzebuję generatora naprawdę dużych liczb pierwszych, ew. ich spis

Potrzebuję dwóch liczb pierwszych P i Q ktorych suma : P * Q = dużaaaa liczba , najlepiej już liczba w granicy 300b .

Pozostało 580 znaków

2019-09-04 09:50
2

spis masz na wiki ;)
https://en.wikipedia.org/wiki/Largest_known_prime_number


Spring? Ja tam wole mieć kontrole nad kodem ᕙ(ꔢ)ᕗ
Haste - mała biblioteka do testów z czasem.

Pozostało 580 znaków

2019-09-04 09:58
1

Generalnie, wikipedia opisuje proces[0]. Bierzesz grupę losowych liczb nieparzystych odpowiedniej wielkości, Sprawdzasz wstępnie podzielność przez małe liczby pierwsze, potem Test Fermata [1] (jest szybki, ale może "przepuścić" liczbę złożoną, jako pierwszą), dalej Miller Rabin Test [2], z odpowiednią ilością testów, aby zminimalizować błąd, 50 będzie aż za dużo imo. Można też zobaczyć na Mersenne Primes [3] - lista dużych liczb pierwszych. Co do implementacji, najlepiej korzystać z bibliotek, Gdybyś chciał to pisać sam, to Możesz rzucić okiem na moje implementacje w Pythonie [4].

[0] https://en.wikipedia.org/wiki/Generating_primes
[1] https://en.wikipedia.org/wiki/Fermat_primality_test
[2] https://en.wikipedia.org/wiki/Miller-Rabin_primality_test
[3] https://www.mersenne.org/primes/
[4] https://github.com/lion137/Py[...]_rabin_fermat_lucas_lehmer.py


Pozostało 580 znaków

2019-09-04 10:11
3

I gdzie jest problem? 300 bajtów to raptem 2400 bitów. Dowolna biblioteka kryptograficzna z RSA wspiera generowanie takich liczb.

ich spis

Brak mi słów. Chcesz 1200 bitowe liczby pierwsze i pytasz o ich spis :D Po pierwsze taki "spis" zajmowałby 2^1200 bitów, czyli 1345508687872 terabajty. Po drugie, gdyby taki spis istniał to RSA (i inne algorytmy oparte o faktoryzacje) dla liczb tego rozmiaru byłoby złamane.

Jeszcze jedna sprawa: potrzebujesz porządne liczby pierwsze a nie dowolne. Najlepiej safe-prime jakieś. Bo zauważ że to nie problem zrobić:

p = gmpy2.next_prime(2**1200)
q = gmpy2.next_prime(p)

Dostaniesz w ten sposób dwa duże primy p,q których iloczyn będzie miał te twoje 2400 bitów. Tylko że bezpieczeństwo tego jest zerowe :D


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...
edytowany 1x, ostatnio: Shalom, 2019-09-04 10:13

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 1, gości: 0, botów: 0

Użytkownik: radb