Generowanie liczby pierwszej. Opcje

[evo]

Potrzebuje wygenerowac dwie bardzo duze liczby pierwsze. I nie weim jak to zrobic.

W javie jest metoda BigInteger.isProbablePrime() lecz w php nic nie moge znalezc.

Czy jest jakis trick jak to zrobic, czy musze generowac liczby losowo i jesli jest nieparzysta to testowac jej pierwszosc a do tego sam musze zimplementowac algorytm na podstawie jakiejs metody np. Fermata.
Czy sa juz jakies zimplementowane metody na to?


Interesuje mnie rowniez jak generuje sie liczby pierwsze w programach kryptograficznych.

[cadavre]

Po bardzo ciężkich 10. sekundach poszukiwań znalazłem:

http://newbc.blackcode.com/forum/index.php...art=0&rid=0
http://pl.wikipedia.org/wiki/Liczba_pierwsza (i prosty do przepisania na php kod C oraz naście algorytmów)

[mike]

A jaki to ma związek z php5?
Przenoszę na php.

[evo]

bo szukam rozwiazania dla PHP5 , a ze dawno w php nie pisalem to myslalem ze moze sa jakies biblioteki dla PHP5 ,ktorych w PHP4 nie ma i dlatego tam napisalem.


@cadavre
To przeczytaj ten artykul ktory podales oraz te
http://en.wikipedia.org/wiki/Prime_number#Primality_tests
http://en.wikipedia.org/wiki/AKS_primality_test
http://en.wikipedia.org/wiki/Fermat_primality_test
http://en.wikipedia.org/wiki/Lucas-Lehmer_test
http://en.wikipedia.org/wiki/Solovay-Strassen_primality_test
http://en.wikipedia.org/wiki/Miller-Rabin_primality_test

i zastanow sie jaki ile czasu zajelo by testowanie liczb 128bitowych na ich pierwszoc podanym przez ciebie sposobem

poza tym php juz sie wyklada na 32bitowych liczbach przy obliczaniu modular exponentiation , ktore jest potrzebne do przeprowadzenia kazdego z tych testow.

NIc dlubie dalej i napisze sam cos opierajac sie na BCMath.

Ten post edytował evo 5.12.2006, 00:29:31

[cadavre]

Nie założyłeś jakie liczby mają to być. Po co Ci aż takie duże?

[siemakuba]

gmp_prob_prime" title="Zobacz w manualu php" target="_manual z http://pl.php.net/manual/pl/ref.gmp.php

funkcja sprawdza czy liczba prawdopodobnie jest liczą pierwszą. Rozszerzenie GMP nie jest standardowo dostępne w php, ale może akurat u ciebie jest / masz możliwość doinstalowania.

pozdr.

[KotDomowy]

Nudziło mi się i miałem wolne 5 minut - to przerobiłem kod na php. Działa w php4 i php5. Zmienna $j jest odpowiedzialna za ilość liczb - tu jest ustawiona na 15000.

[PHP] pobierz, plaintext 
<?php
 
  $tab[0] = 1;   // znalezione liczby pierwsze
   $lim = 0;		// numer kolejnej liczby pierwszej
   $sq = 4;		 // kwadrat liczby tab[lim]
   $i=0; $j=0; $f=0;
 
   printf("%d", $tab[0]);
 
   for($i=3, $j=1; $j<15000; $i+=2)
   {
	   if($i >= $sq)
		   ++$lim; $sq = $tab[$lim] * $tab[$lim];
 
	   for($f=1; $f<$lim; $f++)
		   if($i % $tab[$f] == 0)
			   break;
 
	   if($f >= $lim)
	   {
		   $tab[$j++] = $i;
		   printf(",%d", $i);
	   }
 
   }
 
 
?>
[PHP] pobierz, plaintext 

Nuszi

Ten post edytował KotDomowy 6.12.2006, 20:02:07

[evo]

@siemakuba

Dzieki, za info. Przegapilem GMP przeszukujac manual.


@KotDomowy

Dziekuje rowniez


@cadavre
Bo male latwiej/szybciej sie faktoryzuje