🚀 go-pugleaf

On 04.06.2006, Bogdan (bogdro) <bogdan@bogdan.pl> wrote:
> zrn napisał(a):
>> Witam!
>> Do mojego programu (DOS/Windows) potrzebuję wstawki asemblerowej
>> sprawdzającej czy dana 1024 bitowa liczba jest pierwsza. Liczba jest dana
>> w postaci tablicy zer lub jedynek.
>> Z asemblera jestem mniej niż cienki.
>> Proszę o pomoc, wskazówki, namiary itp.
>
>  Na myśl przychodzi mi najprostszy (czyli też najdłuższy) sposób:
> dzielenie podanej liczby przez wszystkie liczby nieparzyste mniejsze
> równe od liczba/2 (== liczba >> 1).
>  Jeśli ostatni bit = 0, to wiesz, że liczba dzieli się przez 2, więc
> pierwsza nie jest.
>  Omówienie operacji wielokrotnej precyzji znajdziesz m.in. w książce
> Randalla Hyde'a "Art of Assembler", wersja 32-bitowa,
> http://webster.cs.ucr.edu.
>
>  Są też inne sposoby. Słyszałem o teście Fermata, ale złożoność
> problemu nie jest banalna.

Test Fermata (Rabina-Millera, znacznie skuteczniejszy, też) to test
probabilistyczny. Z zerową szansą uznania liczby pierwszej za złożoną.
Niespecjalnie złożony, nawiasem mówiąc.

> W końcu to dzięki złożoności takich testów
> (i faktoryzacji liczb) szyfr RSA żyje jeszcze i ma się dobrze :)

Jakiej znowu złożoności? Ocena pierwszości zadanej liczby to problem
klasy P, o czym wiadomo od paru lat. Zdaje się, że to był wykładnik
rzędu 10, ale to jest wielomian, a nie coś większego. RSA zresztą nie
opiera bezpieczeństwa o trudność stwierdzenia, czy dana liczba jest
pierwsza (co jest łatwe), tylko właśnie o trudność rozkładu dużych
(specjalnie wybieranych) liczb na czynniki pierwsze.

-- 
Feel free to correct my English
Stanislaw Klekot