Pomoc - Szukaj - Użytkownicy - Kalendarz
Pełna wersja: Generowanie liczby pierwszej.
Forum PHP.pl > Forum > PHP
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. winksmiley.jpg


@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 tongue.gif

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.
cadavre
Nie założyłeś jakie liczby mają to być. tongue.gif 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.

  1. <?php
  2.  
  3. $tab[0] = 1;  // znalezione liczby pierwsze
  4.  $lim = 0; // numer kolejnej liczby pierwszej
  5.  $sq = 4;  // kwadrat liczby tab[lim]
  6.  $i=0; $j=0; $f=0;
  7.  
  8.  printf("%d", $tab[0]);
  9.  
  10.  for($i=3, $j=1; $j<15000; $i+=2)
  11.  {
  12.  if($i >= $sq)
  13.  ++$lim; $sq = $tab[$lim] * $tab[$lim];
  14.  
  15.  for($f=1; $f<$lim; $f++)
  16.  if($i % $tab[$f] == 0)
  17.  break;
  18.  
  19.  if($f >= $lim)
  20.  {
  21.  $tab[$j++] = $i;
  22.  printf(",%d", $i);
  23.  }
  24.  
  25.  }
  26.  
  27.  
  28. ?>


Nuszi
evo
@siemakuba

Dzieki, za info. Przegapilem GMP przeszukujac manual.


@KotDomowy

Dziekuje rowniez winksmiley.jpg


@cadavre
Bo male latwiej/szybciej sie faktoryzuje tongue.gif
To jest wersja lo-fi głównej zawartości. Aby zobaczyć pełną wersję z większą zawartością, obrazkami i formatowaniem proszę kliknij tutaj.
Invision Power Board © 2001-2025 Invision Power Services, Inc.