🚀 go-pugleaf

zrn wrote:
> Witam!
> Do mojego programu (DOS/Windows) potrzebuję wstawki asemblerowej
> sprawdzającej czy dana 1024 bitowa liczba jest pierwsza. Liczba jest dana

Mówisz dowolna liczba od 0 do 
179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137215?
(-;

-- 
Pozdrawiam

zrn wrote:
> 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.

Wskazówka: skoro "jesteś cienki" - napisz to w innym języku.

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

 Podstawy języka znajdziesz na mojej stronie:
http://rudy.mif.pg.gda.pl/~bogdro.

-- 
Pozdrawiam, Bogdan                                  (Linux i FreeDOS)
Kurs assemblera x86 (DOS i Linuks): http://rudy.mif.pg.gda.pl/~bogdro
Grupy dyskusyjne o asm:  pl.comp.lang.asm alt.pl.asm alt.pl.asm.win32
Prawdziwy, bezpieczny komunikator:                   www.JabberPL.org

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

>> Witam!
>> Do mojego programu (DOS/Windows) potrzebuję wstawki asemblerowej
>> sprawdzającej czy dana 1024 bitowa liczba jest pierwsza. Liczba jest
>> dana
>
> Mówisz dowolna liczba od 0 do
> 179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137215?
> (-;

skąd wiesz, czy nie od
-89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112068608
do
89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112068607
?


-- 
Azarien

Wiktor S. napisał(a):
> >> Witam!
> >> Do mojego programu (DOS/Windows) potrzebuję wstawki asemblerowej
> >> sprawdzającej czy dana 1024 bitowa liczba jest pierwsza. Liczba jest
> >> dana
> >
> > Mówisz dowolna liczba od 0 do
> > 179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137215?
> > (-;
>
> skąd wiesz, czy nie od
> -89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112068608
> do
> 89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239858152417678164812112068607
> ?
>
>
> --
> Azarien

Ponieważ liczba pierwsza jest liczbą NATURALNĄ, a nie całkowitą,
zatem nie może być ujemna!

Użytkownik "zrn" <zr.nowak@neostrada.pl.atoutnij> napisał w wiadomości news:e5uk4t$dfl$1@atlantis.news.tpi.pl...
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.
zrn.


Gwoli wyjaśnienia, chodzi o dowolną liczbę naturalną między 1 a 1024 bitową  (same jedynki)
daną w postaci łańcucha - zawierającego zera albo jedynki.
Sposób sprawdzania czy liczba dzieli się przez liczby nieparzyste do sqrt(n) a nie n/2 jest dobry.
Wiem jak to zrobić w innym języku ale właśnie ten fragment musi być w asemblerze.
zrn.