Member Avatar for polinolin

Hello dude. Happy New Year. I want to asking about generating primes algorithm. Can you advice tell me what the fast generating primes algorithm except Sieve of Eratosthenes algorithm? thank you. i want to apply the algorithm to my cryptographic system..

  • 3 Contributors
  • 4 Replies
  • 122 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by polinolin

Dani AI

Generated

Good starts from and — their PHP trial-division loop is fine for finding small primes quickly on a single machine. That approach, and micro-optimizations that skip evens, can beat a naive sieve for modest ranges. For cryptographic use (1024+ bit primes) two different patterns are standard and much safer: (1) generate single large primes on demand using a CSPRNG plus strong primality tests, or (2) enumerate many primes up to N using memory-efficient sieves if you truly need a list.

Typical cryptographic workflow (pseudocode):

choose bit_length
repeat:
  candidate = random_odd(bit_length)    # set top and bottom bit
  if divisible_by_any_small_prime(candidate): continue
  if miller_rabin(candidate, k): return candidate

Use a CSPRNG (PHP random_bytes or libsodium), filter out small-prime factors first, then run a probabilistic primality test such as Miller–Rabin. Miller–Rabin has error at most 4^-k for k independent bases; choose k so the failure probability is negligible (e.g., 2^-80 or better). For extra practical safety many systems use the Baillie–PSW combination (no counterexamples are known). See Miller–Rabin and Baillie–PSW for details: Miller–Rabin, Baillie–PSW.

If the goal is enumerating primes up to some N (not generating large crypto primes), consider a segmented sieve or the Sieve of Atkin for speed/memory trade-offs: Segmented sieve (Eratosthenes), Sieve of Atkin.

Practical PHP advice: do not reinvent crypto. Use GMP/OpenSSL/libsodium functions (for primality testing and secure randomness) rather than raw PHP loops — e.g. gmp_prob_prime and random_bytes. See PHP GMP and randomness docs: gmp_prob_prime, random_bytes. Finally, ensure proper entropy, adequate bit length, and rely on well-tested libraries for key generation rather than hand-rolled code.

Recommended Answers

All 4 Replies

Member Avatar for mikulucky

Hope this helps, can be turned into a function easily.

$startAmount = 0;
$endAmount = 100000;

for ($i = $startAmount; $i <= $endAmount; $i++) 
{
    if($i % 2 != 1) 
    {
      continue;
    }
 
    $d = 3; 
    $x = sqrt($i); 

    while ($i % $d != 0 && $d < $x) 
    {
        $d += 2; 
    }

    if((($i % $d == 0 && $i != $d) * 1) == 0) 
    {
        echo $i.' '; 
    }
 }
commented: great solution +7
Member Avatar for polinolin

Hope this helps, can be turned into a function easily.

$startAmount = 0;
$endAmount = 100000;

for ($i = $startAmount; $i <= $endAmount; $i++) 
{
    if($i % 2 != 1) 
    {
      continue;
    }
 
    $d = 3; 
    $x = sqrt($i); 

    while ($i % $d != 0 && $d < $x) 
    {
        $d += 2; 
    }

    if((($i % $d == 0 && $i != $d) * 1) == 0) 
    {
        echo $i.' '; 
    }
 }

Thanks dude.. Its more fast than Sieve of Eratosthenes algorithm.
its so useful!

Member Avatar for cereal

Just a note, you can go a bit faster changing numbers with variables, a modified version of mikulucky:

<?php
$a = 0;
$b = 1;
$c = 2;
$d = 3;
$endAmount = 100000;

for ($i = $a; $i <= $endAmount; $i++) 
{

    if($i % $c != $b) 
    {
      continue;
    }

    $x = sqrt($i);

    while ($i % $d != $a && $d < $x)
    {
        $d += $b; 
    }

    if((($i % $d == $a && $i != $d) * $b) == $a) 
    {
	echo $i . " ";
    }
 }
?>
Member Avatar for polinolin

Just a note, you can go a bit faster changing numbers with variables, a modified version of mikulucky:

<?php
$a = 0;
$b = 1;
$c = 2;
$d = 3;
$endAmount = 100000;

for ($i = $a; $i <= $endAmount; $i++) 
{

    if($i % $c != $b) 
    {
      continue;
    }

    $x = sqrt($i);

    while ($i % $d != $a && $d < $x)
    {
        $d += $b; 
    }

    if((($i % $d == $a && $i != $d) * $b) == $a) 
    {
	echo $i . " ";
    }
 }
?>

thanks for your modified bro!
its so useful :D

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.