[Boerseun]

Does anybody here have an algorythm/procedure for calculating primes?
I want to code an encryption thingy that's going to depend on me being able to figure out how to code primes into it.

[Qfwfq]

How large?

I once posted and attachment that's very quick for unsigned longs in C, which means up to 4,294,967,295 but for encryption you might be needing larger values. What I posted can also be useful if you need to find the prime factors of larger numbers that don't have any higher prime factors.

[Qfwfq]

Here's my algorithm, with a little on-the-fly, untested change in the allocation scheme so that it always prompts for sieve size. This is a good choice if it's often used for not very large values. For use with the highest values one could also choose to save the sieve to a file for following processes.

#include "stdio.h"
#define lhFF  (0xFFFFFFFF)

typedef unsigned long uLong;

// Copyleft Qfwfq, all rights reversed.

bool nextPrime(uLong& n){
static uLong numFlgs, k, maxPrm = 1,* m_Flgs = 0,
	  I = 0, i = 1, J, j, Q, q, dwi, dwj, dwq, maski = 2, maskj;
 if(n <= 2){
  n = 2;
  return true;
 }
 (n == maxPrm)return true;
 fprintf(stderr, "type in a number of bytes, not more than 268435456:\n");
 while(!m_Flgs){
  scanf("%u", &k);
  numFlgs = k >> 2;
  (k & 3) && (numFlgs++, (k &= ~3), k += 4);
  (k <<= 3)--;
  if(m_Flgs = new uLong[numFlgs]){
   for(uLong ii = 0; ii < numFlgs; ii++)m_Flgs[ii] = lhFF;
   break;
  }
  fprintf(stderr, " couldn't allocate %u bytes!\n\ttype in a lower number:\n", numFlgs << 2);
 }
 if(n < maxPrm){
  uLong ii = (n >> 1), dwii, maskii = 1 << (ii%32), II = ii >> 5, max = (maxPrm >> 1);
  for(; ii < max; II++, maskii = 1){
   dwii = m_Flgs[II];
   for(; maskii && ii <= lhFF; ii++, maskii <<= 1){//		ii = 32II + ii%32
    if(dwii & maskii){
     n = 1 + (ii << 1);
     return true;
    }
   }
  }
 }
 uLong in = n >> 1;
 for(; i <= k; I++, maski = 1){
  dwi = m_Flgs[i];
  for(; maski && i <= k; i++, maski <<= 1){//		i = 32I + i%32
   if(dwi & maski){
    if(i >= in){
     n = maxPrm = 1 + (i << 1);
     return true;
    }
    for(j = (k - i)/((i << 1) + 1), J = (j >> 5), maskj = 1 << (j & 0x1F)
	; j >= i; J--, maskj = 0x80000000){
     dwj = m_Flgs[J];
     for(; maskj && j >= i; j--, maskj >>= 1)//		j = 32J + j%32
      if(dwj & maskj){
       q = ((i*j) << 1) + i + j;
       m_Flgs[Q = (q >> 5)] &= dwq = ~(1 << (q & 0x1F));
       (Q == I) && (dwi &= dwq);
      }
    }
   }
  }
 }
 return false;
}

[Boerseun]

Originally Posted by Qfwfq

How large?

I once posted and attachment that's very quick for unsigned longs in C, which means up to 4,294,967,295 but for encryption you might be needing larger values. What I posted can also be useful if you need to find the prime factors of larger numbers that don't have any higher prime factors.

Doesn't really matter, I suppose.

All I want is the standard logic being used - I want to see if it will be useful. Doesn't even need to be in code. I suppose the standard being used is something like:

1) Add 2 to variable
2) Exclude all even integers
3) See if you can divide variable by x (x being 3)
4) Add 2 to x
5) repeat 3 & 4 until x=variable
6) Go back to 1

This seems like it will take a hell of a long time, but how can you speed this up?

[C1ay]

Originally Posted by Boerseun

Doesn't really matter, I suppose.

All I want is the standard logic being used - I want to see if it will be useful. Doesn't even need to be in code. I suppose the standard being used is something like:

1) Add 2 to variable
2) Exclude all even integers
3) See if you can divide variable by x (x being 3)
4) Add 2 to x
5) repeat 3 & 4 until x=variable
6) Go back to 1

This seems like it will take a hell of a long time, but how can you speed this up?

Actually, you only have to divide the test number by each of the primes that are less than the square root of the number itself to test for primality. Many algorithms do just that after building an initial set of primes using a sieve. There are several tests explained here that can be used for testing primality. GIMPS (site was down when I wrote this) has a downloadable program for searching out primes as part of their effort to find Mersenne primes and I believe the source code is available.

[Qfwfq]

Originally Posted by Boerseun

This seems like it will take a hell of a long time, but how can you speed this up?

Indeed, this would be slow! Mine is an example of Eratosthenes' sieve which works by casting out multiples, rather than by trial division. You can find many hits with Google, I tied just now and got more than 30 thousand so I'll let you do some reading instead of posting too much detail here. Basically, with an array of flags, you hardly need to even multiply.

My sample uses a flag bit for each odd number starting from 3 and fairly standard arithmetic tricks but it has a non-standard iteration that I devised years ago, which seems to help in speed even in RAM and should save more time in an implementation using a file as a large sieve. I never got around to writing such an implementation for larger primes though. As it is, it doesn't perform well if the sieve in RAM gets swapped more than a bit, the iteration fiercely disagrees with the OS swapping algorithm.

[Chacmool]

Originally Posted by Boerseun

Does anybody here have an algorythm/procedure for calculating primes?
I want to code an encryption thingy that's going to depend on me being able to figure out how to code primes into it.

What is a "thingy"? It sounds highly scientific to me...

[Turtle]

___GETE Where to start? How about the thingy? The question then is who do you intend to keep secrets from? The more powerful the adversary, the more powerful the encryption needed.
___While some "shortcuts" exist for finding primes, it is essentially a factoring problem & moreover it remains a "hard" problem in mathematics. This is a fancy way to say there exist no real shortcuts. The best minds take a crack at this problem regularly, as they have for millenia, & yet it remains hard.
___On Eratosthenes' sieve, I reiterate what Q touched on in reference to his code; you must set your upper search limit before you begin.
___All in all, your thingy question is rather silly Boerseun. Why do you tease us so?

[Turtle]

___I have some additional thoughts on this topic As if! Anyway, it is the study of the primes under Katabataks.
http://hypography.com/forums/physics-and-mathematics/1343-katabatak-math-an-exploration-in-pure.html

___Staying in base ten, the K(prime) never has transforms of K(3), K(6), or K(9). Since the Katabatak function base ten is congruent modulo 9, one has only to recursively sum the digits of a suspected prime (which you have already visually sieved to include only those with ending digits 1, 3, 7, or 9), & so exclude those with K's 3, 6, or 9 as composite numbers.
___This procedure is sufficient for pencil & paper using numbers as large as a hundred digits or more; note that the K function does not exclude all composites under any one base; employing succesive bases is necessary for that.
___Finally, the analysis of the Katabatak transsforms of primes reveals patterns that further illuminate their nature; it is a rather detailed study however that is for later exposition in the Katabatak thread here exclusively at Hypography.

[Qfwfq]

Originally Posted by Turtle

This procedure is sufficient for pencil & paper using numbers as large as a hundred digits or more; note that the K function does not exclude all composites under any one base; employing succesive bases is necessary for that.

To actually compute the digits of a given number in different bases would take computation time itself, but you have given me an idea that could save some trial divisions in primality testing!