Generating large prime numbers

prismspecs

I'm wondering if anyone has used Processing to generate very large prime numbers at random (for use in encryption, or at least a creative nod thereto). I found a little info for Java, but it seems Processing lacks the libs to carry it out.

import java.math.BigInteger;

BigInteger definitePrime(int bits, Random rnd) {
    BigInteger prime = new BigInteger("4");
    while(!isPrime(prime)) prime = BigInteger.probablePrime(bits,rnd);
    return prime;
}

It doesn't understand type Random nor the isPrime call. Thoughts?

Chrisir

here, lots of flaws, but maybe it helps...

import java.math.*;
import java.math.BigInteger;
import java.util.*;

BigInteger definitePrime(int bits, Random rnd) {

  BigInteger prime = new BigInteger("4");

  while (!isPrime (prime)) 
    prime = BigInteger.probablePrime(bits, rnd);

  return prime;
}

public static Boolean isPrime(BigInteger num) {
  // http:  //  professorjava.weebly.com/isprime.html 
  //method signature. returns Boolean, true if number isPrime, false if not
  if (num.intValue()==2) { //for case num=2, function returns true. detailed explanation underneath
    return(true);
  }
  for (int i=2;i<=(int)Math.sqrt(num.intValue())+1;i++) { //loops through 2 to sqrt(num). All you need to check- efficient
    if (num.intValue()%i==0) { //if a divisor is found, its not prime. returns false
      return(false);
    }
  }
  return(true); //if all cases don't divide num, it is prime.
}

void setup() {
  // create a random object
  Random rnd = new Random();

  println ( definitePrime (29, rnd));
}

Chrisir

see

http://www.tutorialspoint.com/java/math/biginteger_probableprime.htm

http://professorjava.weebly.com/isprime.html

Chrisir

main problem in my sketch is probably that I often use .intValue() ...

;-)

koogs

this puzzles me

i++

(not just in chrisir's code - all the examples i found on the web also did it)

you don't have to check every number as the divider - if n % 4 = 0 then n % 2 would also have been 0, so you don't need to check i = 4. or any other multiple of 2. using i += 2 would halve the numbers you'd check (having made sure n % 2 != 0)

public static Boolean isPrime2(BigInteger num) {
  int count = 0;
  if (num.intValue() == 2) {
    return(true);
  }
  if (num.intValue() %2 == 0) {
    return(false);
  }
  for (int i = 3 ; i <= (int)Math.sqrt(num.intValue()) + 1 ; i += 2) {
    println(++count);
    if (num.intValue() % i==0) {
      return(false);
    }
  }
  return(true);
}

(in fact, you only have to check prime numbers as the divisors, 2, 3, 5, 7, 11 etc. and then only up to the sqrt of the number under test.)

_vk

Once I wrote a function like that with my father : P

http://forum.processing.org/one/topic/how-would-i-write-a-function-to-determine-whether-a-number-is-prime-s.html

GoToLoop

Made some tweaks for the sake of speed: :ar!
P.S.: Oops! Little l8! @koogs was faster HEHE! But I guess mine is a bit speedier! O:-)
While I'm at it @koogs, lemme ask ya why don't you have an avatar yet?! :O)

/**
 * isBigIntegerPrime (v3.01)
 * by  PrismSpecs & Chrisir (2014/Oct/09)
 * mod GoToLoop & Koogs
 *
 * forum.Processing.org/two/discussion/7526/
 * generating-large-prime-numbers
 *
 * www.TutorialsPoint.com/java/math/
 * biginteger_probableprime.htm
 *
 * ProfessorJava.Weebly.com/isprime.html
 */

import java.math.BigInteger;
import java.util.Random;

static final int BITS = 50;
final Random rnd = new Random();

void setup() {
  noLoop();
  frameRate(100);
}

void draw() {
  print(definitePrime(BITS, rnd) + " - ");
}

void keyPressed() {
  redraw();
}

static final BigInteger definitePrime(int bits, Random rnd) {
  BigInteger prime;
  while (!isPrime(prime = BigInteger.probablePrime(bits, rnd)));
  return prime;
}

static final boolean isPrime(BigInteger num) {
  long val = num.longValue();
  if (val == 2l)         return true;
  if ((val & 1l) == 0l)  return false;

  long i = 1l, ii = (long) Math.sqrt(val) + 1l;
  while ((i+=2l) <= ii)  if (val%i == 0l)  return false;

  return true;
}

MenteCode

@koogs: You would be correct on this matter. Though line 6 through 8 would be unnecessary. That is, if you actually trust your code. :P

Saying that, meaning that the JVM might screw with some math. But I trust Java way more than that.

@Chrisir: There's actually a way of not using intValue(), and no, it's not what you think. It actually involves doing the opposite of taking a square root.

Multiplying 2 numbers is a much cheaper operation than a square root. So instead of:

for (int i = 3 ; i <= (int)Math.sqrt(num.intValue()) + 1 ; i += 2) {
//koogs' code that I copied. :P

you can do:

for (long i = 3 ; i * i <= num; i += 2) {

So, in the end, having worked a lot with prime numbers, the most optimized method, if you're not checking millions of different numbers, for finding prime numbers would be:

public static boolean isPrime(long num) {
    if (num == 2) {
        return true;
    }

    for (long i = 3; i * i <= num; i += 2) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

Which determines the 18 digit prime number 981168724994134051 in 4.6 seconds. Fairly fast for such a large number.

---

Now, for actually generating prime numbers, you could use an actual prime number array generator.

If you are going to test more than a million different numbers for primality, then actually generating a test array once will be a big help. Cuts a lot of corners v.s. using the isProbablePrime() method. I won't explain why this is so, as there is quite a bit of logic that arises from other bits of logic, etc.

public static int[] ESieve(int upperLimit) {
    int[] primes = new int[(upperLimit + 1) / 2];
    int index = 1;
    primes[0] = 2;

    loop:
    for(int i = 3; i <= upperLimit; i += 2) {
        for(int p : primes) {
            if(p * p > i) break;
            if(i % p == 0) continue loop;
        }

        primes[index] = i;
        index++;
    }

    return Arrays.copyOfRange(primes, 0, index);
}

Then, you could use the resulting array, and test numbers against it. Just iterate over elements, and check if the tested number is prime.

I recommend that you don't change the data type of the method above though. Your machine might not be able to handle the whole array, otherwise.

asimes

In the link _vk posted PhiLho mentioned the Sieve of Eratosthenes which I was about to suggest. The general idea is to avoid testing numbers that are divisible by something already tested (what koogs said).

Say you try val%2 == 0 and val is not divisible by 2. It doesn't make any sense to try val%4 == 0, val%6 == 0, val%8 == 0, etc. because val%2 == 0 already failed. Here is a GIF that shows the idea: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#mediaviewer/File:Sieve_of_Eratosthenes_animation.gif

koogs

MenteCode @koogs: You would be correct on this matter. Though line 6 through 8 would be unnecessary. That is, if you actually trust your code.

without line 6 it doesn't check that num % 4 == 0 (or 6, or 8...)

the first bit checks it's not exactly 2 and the main loop starts from 3 and goes up 2 at a time.

--

be wary that the SoE requires storage, albeit one bit per integer. so it might not be suitable for really large prime numbers - 981168724994134051 bits is still a lot 8)

MenteCode

It's just that I don't see there being a time when adding 2 to an odd number will make it even.

I.e. 8001 + 2 will never be 8004.

So basically, 4, 6, 8, and all others will just be skipped automatically. 3+2 = 5, 5 + 2 = 7, and 7 + 2 = 9. And since we're starting with 3, everything deals with itself on its own.

koogs

try it!

this is chrisir's original post calling my isPrime2() instead of his original

// chrisir + acd
import java.math.*;
import java.math.BigInteger;
import java.util.*;

BigInteger definitePrime(int bits, Random rnd) {

  BigInteger prime = new BigInteger("4");

  while (!isPrime2 (prime)) 
    prime = BigInteger.probablePrime(bits, rnd);

  return prime;
}

public static Boolean isPrime(BigInteger num) {
  // http:  //  professorjava.weebly.com/isprime.html 
  //method signature. returns Boolean, true if number isPrime, false if not
  if (num.intValue()==2) { //for case num=2, function returns true. detailed explanation underneath
    return(true);
  }
  for (int i=2;i<=(int)Math.sqrt(num.intValue())+1;i++) { //loops through 2 to sqrt(num). All you need to check- efficient
    if (num.intValue()%i==0) { //if a divisor is found, its not prime. returns false
      return(false);
    }
  }
  return(true); //if all cases don't divide num, it is prime.
}

// acd's bit
public static Boolean isPrime2(BigInteger num) {
  int count = 0;
  if (num.intValue() == 2) {
    return(true);
  }
  /** mentecode doesn't think i need this
  if (num.intValue() %2 == 0) {
    return(false);
  }
  */
  for (int i = 3 ; i <= (int)Math.sqrt(num.intValue()) + 1 ; i += 2) {
    if (num.intValue() % i==0) {
      return(false);
    }
  }
  return(true);
}

void setup() {
  // create a random object
  Random rnd = new Random();

  println ( definitePrime (29, rnd));
}

it reports 4 as a prime, which it patently isn't.

(i think you are thinking that this is the code that is generating the numbers. it's not, it's the code that's checking whether the numbers are prime)

MenteCode

(i think you are thinking that this is the code that is generating the numbers. it's not, it's the code that's checking whether the numbers are prime)

You would be right. :\">

If only I had actually tested my code above. Mine has the same mistake. :-\"

And it's not that I thought it was generating primes. But for some reason, my mind just swapped the two, or something. So yes. You indeed need that check. My mistake.

koogs

i've been profiling the above, just out of curiosity. and there's really not a lot in any of the optimisations, even 128 bit numbers are coming back in 10s of milliseconds or so. even my optimisation of skipping half the factors doesn't seem to make much difference. i think something else (creation of draw window? BigInteger.probablePrime?) is causing a lot of noise and making decent profiling difficult. i did notice this at higher bit rates though:

  BigInteger b = new BigInteger("183972267825065276461950095037660073391");

  println(gotoLoopIsPrime(b));
  println(acdIsPrime(b));
  println(menteIsPrime(b));
  println(chrisirIsPrime(b));

false, true, true, true...

same with:

193336537508320564286072882165085504181
254344737305704076432103377667681460507
327196556395952306894399796628420507577
198200387859470846145471591029883294239

(starts around 40 bits (1068714100087 for instance) and slows the whole thing down because it keeps rejecting good primes)

GoToLoop

My isPrime() version uses long, which is 63 bits at most. Your BigInteger is 128, completely unreliable!
In order to amend that, I've expanded my version to deal w/ int, long and BigInteger ranges: :-bd

/**
 * isBigIntegerPrime (v4.24)
 * by  PrismSpecs & Chrisir (2014/Oct/09)
 * mod GoToLoop & Koogs
 *
 * forum.Processing.org/two/discussion/7526/
 * generating-large-prime-numbers#Item_14
 *
 * www.TutorialsPoint.com/java/math/
 * biginteger_probableprime.htm
 *
 * ProfessorJava.Weebly.com/isprime.html
 */

import java.math.BigInteger;
import java.util.Random;

static final int BITS = 56, CERTAINTY = 128;
final Random rnd = new java.security.SecureRandom();

void setup() {
  noLoop();
  frameRate(100);
  println("Bits: " + BITS);
}

void draw() {
  print(definitePrime(BITS, rnd) + " - ");
}

void keyPressed() {
  redraw();
}

static final BigInteger definitePrime(int bits, Random rnd) {
  BigInteger prime;
  while (!isPrime(prime = BigInteger.probablePrime(bits, rnd)));
  return prime;
}

static final boolean isPrime(BigInteger n) {
  int bits = n.bitLength();
  return bits < 32? isPrimeInt(n.intValue())
    : bits < 63? isPrimeJS(n.longValue())
      : n.isProbablePrime(CERTAINTY);
}

static final boolean isPrimeInt(int n) {
  if (n <= 3)  return n >= 2;
  if ((n&1) == 0 | n%3 == 0)  return false;

  int i = -1, sqrtN = (int)Math.sqrt(n) + 1;
  while ((i+=6) <= sqrtN)
    if (n%i == 0 || n%(i+2) == 0)  return false;

  return true;
}

static final boolean isPrimeLong(long n) {
  if (n <= 3L)  return n >= 2L;
  if ((n&1L) == 0L | n%3L == 0L)  return false;

  int i = -1, sqrtN = (int)Math.sqrt(n) + 1;
  while ((i+=6) <= sqrtN)
    if (n%i == 0L || n%(i+2) == 0L)  return false;

  return true;
}

static final boolean isPrimeJS(long n) {
  if (n <= 5L)  return n >= 2L & n != 4L;
  if ((n&1L) == 0L | n%3L == 0L | n%5L == 0L)  return false;

  int i = -23, sqrtN = (int)Math.sqrt(n) + 1;
  while ((i+=30) <= sqrtN)  if
    ( n%i      == 0L
    | n%(i+4)  == 0L
    | n%(i+6)  == 0L
    | n%(i+10) == 0L
    | n%(i+12) == 0L
    | n%(i+16) == 0L
    | n%(i+22) == 0L
    | n%(i+24) == 0L)       return false;

  return true;
}

MenteCode

Alright, everyone. Try your hand at the method one of JavaScripter's calculators use:

public static boolean isPrimeJS(long num) {
    if (num == 2 | num == 3 | num == 5) return true;
    if (num % 2 == 0) return false;
    if (num % 3 == 0) return false;
    if (num % 5 == 0) return false;
    for (long i = 7; i * i <= num; i += 30) {
        if (num % i == 0) return false;
        if (num % (i + 4) == 0) return false;
        if (num % (i + 6) == 0) return false;
        if (num % (i + 10) == 0) return false;
        if (num % (i + 12) == 0) return false;
        if (num % (i + 16) == 0) return false;
        if (num % (i + 22) == 0) return false;
        if (num % (i + 24) == 0) return false;
    }

    return true;
}

It was originally intended to return the least prime factor of a number. I've even tested this method on my TI-83, and it still works very well.

Now, I've transformed that into what you see above.

Personally, I still have trouble believing that 7 + 30x (that expression alone) generates valid primes every time (I'd think that this is based on a modified version of "sexy primes").

Also, when you test this, I will warn you that you have to let the CPU warm up to have an equal comparison of this, and the methods above. It has achieved speeds up to 3.5x of my original code (on my workstation, at least).

Edit: Ah yes. Once again, I forget to actually check 2, 3, and 5. Fixed.

GoToLoop

Adapted for my example too! :ar! Dunno if it's any faster though... :-@
Warning: Since my version is using int for the iterator, it doesn't work for 63-bit long values!

static final boolean isPrimeJS(long n) {
  if (n == 2L | n == 3L | n == 5L)  return true;
  if (n < 2L || (n&1L) == 0L
    || n%3L == 0L || n%5L == 0L)    return false;

  int i = -23, sqrtN = (int)Math.sqrt(n) + 1;
  while ((i+=30) <= sqrtN)  if
    (  n%i      == 0L
    || n%(i+4)  == 0L
    || n%(i+6)  == 0L
    || n%(i+10) == 0L
    || n%(i+12) == 0L
    || n%(i+16) == 0L
    || n%(i+22) == 0L
    || n%(i+24) == 0L)      return false;

  return true;
}

MenteCode

Well, here's a bit of a test. An even match between the 2 algorithms.

Most of the the algorithms, excluding the one from JavaScripter, were for the most part the same, so I just took the most optimized one (feel free to replace it if you have a better one).

Here's the test code. I have a relatively high end computer, now, so isPrime() took 13.5 seconds to run, whereas isPrimeJS() to 6.7 seconds.

double test1, test2;

void setup() {
  println("Warming up the CPU...");
  warmup(10000000); //Let's get that CPU warmed up, so all comparisons are equal.
  println("Initializing nanosecond timer...\n");
  println("Done. Prime being tested is 9051643576320000001 (19 digits long).");
  println("The prime number is fairly large, so be patient as the test occurs.\n");
  Stopwatch s = new Stopwatch();

  println("First algorthim. The original code, isPrime().");
  println("\nStart.");
  s.start();
  println(isPrime(9051643576320000001L));
  s.stop();
  println("Test complete. Time taken: " + s.getNanoTime() / 1000000d + " ms.\n");
  test1 = s.getNanoTime() / 1000000d;

  println("Second algorthim. Modified from JavaScripter, isPrimeJS().");
  println("\nStart.");
  s.start();
  println(isPrimeJS(9051643576320000001L));
  s.stop();
  println("Test complete. Time taken: " + s.getNanoTime() / 1000000d + " ms.");
  test2 = s.getNanoTime() / 1000000d;

  boolean test1Wins = test1 < test2;
  String winner = (test1Wins ? "IsPrime()" : "IsPrimeJS()");
  String runnerUp = (test1Wins ? "IsPrimeJS()." : "IsPrime().");
  double time = (test1Wins ? test1 : test2);
  double ratio = (test1Wins ? test2 / test1 : test1 / test2);
  println("Winner: " + winner + ", with a time of: " + time + " milliseconds, which is " + String.format("%.5f", ratio) + " faster than " + runnerUp);
}

void warmup(int upperLimit) { //Sieve of Eratosthenes, used as a moderately computation intensive warm up.
  int[] primes = new int[(upperLimit + 1) / 2];
  int index = 1;
  primes[0] = 2;

loop:
  for (int i = 3; i <= upperLimit; i += 2) {
    for (int p : primes) {
      if (p * p > i) break;
      if (i % p == 0) continue loop;
    }

    primes[index] = i;
    index++;
  }
}

//The original code
public static boolean isPrime(long num) {
  if (num == 2) return true;
  if ((num & 1l) == 0) return false;

  for(long i = 3; i * i < num; i += 2) if(num % i == 0) return false;

  return true;
}

//JavaScripter's code
public static boolean isPrimeJS(long num) {
  if (num % 2 == 0) return false;
  if (num % 3 == 0) return false;
  if (num % 5 == 0) return false;
  for (long i = 7; i * i <= num; i += 30) {
    if (num % i == 0) return false;
    if (num % (i + 4) == 0) return false;
    if (num % (i + 6) == 0) return false;
    if (num % (i + 10) == 0) return false;
    if (num % (i + 12) == 0) return false;
    if (num % (i + 16) == 0) return false;
    if (num % (i + 22) == 0) return false;
    if (num % (i + 24) == 0) return false;
  }

  return true;
}

class Stopwatch {
  private long startTime;
  private long stopTime;

  public void start() {
    startTime = System.nanoTime();
    stopTime = startTime;
  }

  public void stop() {
    stopTime = System.nanoTime();
  }

  public long getNanoTime() {
    return stopTime - startTime;
  }
}

The Stopwatch class is there, because it times the algorithms in nanoseconds, rather than milliseconds. This helps get a more accurate reading.

Tell us what you get.

GoToLoop

In order to properly warm-up, we gotta call the actual methods being tested! :-w

isPrime(62131125996267401L);
isPrimeJS(62131125996267401L);
isPrime(46331401803043001L);
isPrimeJS(46331401803043001L);
isPrime(38924154034357817L);
isPrimeJS(38924154034357817L);

I've replaced both isPrime() & isPrimeJS() w/ my own versions.
I've only had to modify them to use a long iterator since 9051643576320000001L is a 63-bit value!
If that was at most 62-bit, my unmodified int versions coulda been used instead! :-<
Probably would net slightly better results methinks...

Indeed, isPrimeJS() is the clear winner. W/ my version slightly faster than the 1 you tested with! \m/
And my own modified isPrimeLong(), using 6 step iterator jumps is much faster than the 1 using 2 only!

P.S.: My isPrimeJS() when using | rather than || in the chained check expression is a few millis faster! :P
However, it's a tiny slower for the isPrimeLong()'s case! #-o

double test1, test2;

void setup() {
  println("Warming up the CPU...");
  warmup(10000000); //Let's get that CPU warmed up, so all comparisons are equal.

  isPrimeLong(62131125996267401L);
  isPrimeJS(62131125996267401L);
  isPrimeLong(46331401803043001L);
  isPrimeJS(46331401803043001L);
  isPrimeLong(38924154034357817L);
  isPrimeJS(38924154034357817L);

  println("Initializing nanosecond timer...\n");
  println("Done. Prime being tested is 9051643576320000001 (19 digits long).");
  println("The prime number is fairly large, so be patient as the test occurs.\n");

  Stopwatch s = new Stopwatch();

  println("First algorthim. The original code, isPrime().");
  println("\nStart.");
  s.start();
  println(isPrimeLong(9051643576320000001L));
  s.stop();
  println("Test complete. Time taken: " + s.getNanoTime() / 1000000d + " ms.\n");
  test1 = s.getNanoTime() / 1000000d;

  println("Second algorthim. Modified from JavaScripter, isPrimeJS().");
  println("\nStart.");
  s.start();
  println(isPrimeJS(9051643576320000001L));
  s.stop();
  println("Test complete. Time taken: " + s.getNanoTime() / 1000000d + " ms.");
  test2 = s.getNanoTime() / 1000000d;

  boolean test1Wins = test1 < test2;
  String winner = (test1Wins ? "IsPrime()" : "IsPrimeJS()");
  String runnerUp = (test1Wins ? "IsPrimeJS()." : "IsPrime().");
  double time = (test1Wins ? test1 : test2);
  double ratio = (test1Wins ? test2 / test1 : test1 / test2);
  println("Winner: " + winner + ", with a time of: " + time
    + " milliseconds, which is " + String.format("%.5f", ratio)
    + " faster than " + runnerUp);

  exit();
}

void warmup(int upperLimit) {
  int[] primes = new int[(upperLimit + 1) / 2];
  int index = 1;
  primes[0] = 2;

loop:
  for (int i = 3; i <= upperLimit; i += 2) {
    for (int p : primes) {
      if (p * p > i) break;
      if (i % p == 0) continue loop;
    }

    primes[index] = i;
    index++;
  }
}

//The original code
static final boolean isPrimeLong(long n) {
  if (n <= 3L)  return n >= 2L;
  if ((n&1L) == 0L | n%3L == 0L)  return false;

  long i = -1L, sqrtN = (long)Math.sqrt(n) + 1L;
  while ((i+=6L) <= sqrtN)
    if (n%i == 0L || n%(i+2L) == 0L)  return false;

  return true;
}

//JavaScripter's code
static final boolean isPrimeJS(long n) {
  if (n <= 5L)  return n >= 2L & n != 4L;
  if ((n&1L) == 0L | n%3L == 0L | n%5L == 0L)  return false;

  long i = -23L, sqrtN = (long)Math.sqrt(n) + 1L;
  while ((i+=30L) <= sqrtN)  if
    ( n%i       == 0L
    | n%(i+4L)  == 0L
    | n%(i+6L)  == 0L
    | n%(i+10L) == 0L
    | n%(i+12L) == 0L
    | n%(i+16L) == 0L
    | n%(i+22L) == 0L
    | n%(i+24L) == 0L)       return false;

  return true;
}

class Stopwatch {
  private long startTime;
  private long stopTime;

  public void start() {
    startTime = System.nanoTime();
    stopTime = startTime;
  }

  public void stop() {
    stopTime = System.nanoTime();
  }

  public long getNanoTime() {
    return stopTime - startTime;
  }
}

prismspecs

You guys are insane. Incredibly helpful, thank you!

MenteCode

Insane. In a good way. ;)

Glad to help. I'm sure others are too.

GoToLoop

I've posted these algorithms in the Ruby's GitHub! Which coincidentally were trying to optimize their prime() implementation: https://github.com/ruby/ruby/pull/736 =:)