Prime numbers

[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!nttype 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]

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]

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]

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]

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 :cup: As if! Anyway, it is the study of the primes under Katabataks.

http://hypography.com/forums/showthread.php?t=1343

 

___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]

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!

[Turtle]

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!

 

Indeed! Sir Q, you have no idea how high a regard I hold for your acknowlegment of useful bits in all my musings. Such is the treasure of a generalist.

[nkt]

___Attached below for a bit, my core code in TurboBasic which I use in my factoring experiments.

I have to wonder why you posted a thumbnail of your code, rather than the code?

 

I had to do this in C at Uni. Rather trivial for small numbers, gets very hard at big numbers.

 

There are lots of simple rules that will generate your basic set for testing. Once your numbers get really big, you want to start doing more complex seive tests. For instance, you can do a short test to tell if a number is divisible by nine. This uses a lot more time than just plodding through the maths for a short number, but for one that is hundreds of digits long, the test is much, much faster.

 

Obviously, you stop testing the prime at the square root of the number, you work from the lower divisors first, you step in a pattern of +2, then throw out every number ending in five.

 

You use a machine that is fast with lots of RAM, and, if you are the NSA or MI5, you probably build custom hardware that can do all this as a huge RAM string, using bit-wise comparisions, which are very very fast compared to other methods.

 

I had an idea for a machine for breaking public key (Hillman-Diffie) encryption. Use a machine that is based on prime numbers instead of real numbers. I'm not even sure it is possible in theory...

 

The other question is how secure are these encryption methods? Can the keys be brute-forced? Do the NSA have a fleet of machines that break 4096 bit systems in two or three days?

 

Consider the speed of a parallel machine based on FPGAs, running at 100MHz. If you are able to write a program that will run through a list of 100,000 primes in every second, an FPGA will let you run hundreds in parallel at the same time. Now imagine ten thousand of those, all working together under the New Mexico desert. Suddenly doesn't seem quite so secure, does it?

 

http://66.102.9.104/search?q=cache:b8lgwnZQkdIJ:www.fpgajournal.com/articles_2005/20050405_cray.htm+fpga+speed&hl=en&client=firefox-a shows us the way things are heading.

[Turtle]

I have to wonder why you posted a thumbnail of your code, rather than the code?

 

___Because it is on a very old machine & I have no end of failures putting it on this machine which isn't mine anyway yada yada yada. So I put it up because I can; it pertains to several ongoing threads I started here involving factoring.

___In reference to encryption, Singh's recent book is very illucidating (The Code Book: The Secret History of Codes and Code-breaking by Simon Singh) . The size of primes, well psuedo primes, is what determines the security of most encryption & wholly depends on knowing what is the fastest computer power available to the enemy & then you know how long it takes them to crack it & then you know your message is safe that long for how big a psuedo prime you chose to encrypt with.

___

[Turtle]

___I referred above to threads here at Hypography that concern primes, & more to the point factoring. Below find the links to these threads:

Strange Numbers:

http://hypography.com/forums/showthread.php?t=1220

 

Statistical Distribution By Factors:

http://hypography.com/forums/showthread.php?t=1410

 

Phat Numbers (pluperfect numbers):

http://hypography.com/forums/showthread.php?t=1473

;)

[Turtle]

___This whole idea is... well, primal. A concept that has occupied people for as long as we have records, as it does now. Our friend Albert claims to have come about some of his insights by imagining himself riding a beam of light & I have come about some of mine by imagining myself with a box of rocks.

___Without reference to written numerals, here is the essence of prime in regard to number, i.e. quantity. It is quantity - how many? - after all that is the core of this. So I seat myself on the ground with a large box of rocks in front of me within reach. [i have a comfortable sit-upon, & polished pea-sized rocks]

___I reach in & take out a double handfull of rocks & pour them in a pile before me. Now I challenge myself to arrange from this pile as many different patterns of piles as possible so that there is never a single stone left, i.e. not in a complete group.

___I now imagine that I am elfin & a double handful is a single stone. There exists just a single arrangement. I take a powder from Carroll to grow a bit; now I grab two stones. I procede to arrange my stones first in a single pile of two, then two piles of one & that is all.

___So taking these steps I progress to ever larger hands & arrangments. With irritating regularity I find some quantities of stones have no arrangements save all in one pile. Those prime quantities.

____In this view I see no short way to see if a pile is prime or not save counting every stone. Even if I grab five stones at a time to count them all, or ten, etc., I must ultimately count them all to find my answer. Every stone counts! :eek:

[CraigD]

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.

Finding large primes for encryption is something I need to do frequently. Most of the time, algorithms implemented in network hardware takes care of it without any attention from me, but, on occasion, I’ve had to do it in application-level code.

 

Here’s a pretty conventional scheme for generating a large prime (I’ve actually used this to generate RSA key pairs, where reasonable but no sub-second response time was acceptable):

1) select a random number of the desired size

2) make sure it’s odd

3) check it using a fast primacy test

4) if step 3 fails, increment the number by 2 and repeat step 3

 

The key to the above, I’m sure you immediately realize, is “a fast primacy test”. You may have already discovered that dividing by every odd number less than the square root of the candidate number is so far from “fast” that it isn’t practical to implement. Fortunately, there are many algorithms that are much faster than this – most prime factoring resource websites can provide you with several. Although far from the fastest, the Rabin-Miller prime test, that’s easy to describe. Here it is as M code:

s m=p-1,j=1 f b=0:1 q:m#2!'m s m=m2

s i=m,E="" f q:'i s E=i#2_E,i=i2

f i=1:1:n d q:p-1'=z

.s a=$r(p-1)+1,z=1 f j=1:1:$l(E)-1 s:$e(E,j) z=z*a#p s z=z*z#p

.s z=z*a#p s:z=1 z=p-1 f j=1:1:b q:p-1=z s z=z*z#p

i p-1=z ;p is (likely to be) prime!

 

Where:

p is the number to be tested

n is the number of times to repeat the test. The probability of a false positive test is 1/(4^n).

 

Notice that, although Rabin-Miller only assures that the probability of a number it judges prime is actually not is arbitrarily small (1/(4^n)), even a fairly small n - less than 50 – the chance of a false positive is smaller than the chance of a random CPU math error, so is effectively zero. Also, notice that the chance of getting a prime at each step #3 is about 2/Log(number), and that RM fails after a non-prime after only 1 iteration, so this algorithm is pretty fast – usually less than 100 iterations.

 

In case you’re unfamiliar with the M programming language, here’s a quick summary:

“s” is the “set” assignment command. “s:expression” means “set if expression true/not 0”

“f b=0:1” means “for b = 0 by 1 to infinity”, set b=0, repeat the rest of the line until told to exit, add 1 to b after each iteration.

“f j=1:1:n” means “for j = 1 by 1 to n”, as above, but exit when j exceeds n.

“q:expression” means “quit (exit the for loop) when expression not zero” (This board’s parse insists on displaying “ : p “ as :eek: )

“+”, “-“, and “*” are the usual plus, minus, and times operators.

“” is the integer division operator, eg: 32=1

“#” is the modulo (integer remainder) operator, eg: 8#5=3

“_” is the concatenation operator, eg: “123”_”456”=”123456”

“d “ and “ .” is the “do block” structure. The lines beginning “ .” are executed before the command following “d “

“$r(n)” returns a random number from 0 to n-1

“$l(e)” returns the length of e

“$e(X,Y) returns the Yth character of X

“i” is the “If” command

“;” is the comment command – everything after it is a comment

 

A free, never-expires implementation of M, known as Cache, can be had at http://titanium.intersystems.com/sc...p=cachedownload, though you must give the vender an email address to get it.

 

Note that M has only 16-20 decimal digit (54-64 bit) precision, so it’s just barely adequate for RSA-128, an old, weak PKencryption. Regardless of the language used to implement a prime generator, most decently strong encryption will require you use some high-precision math library functions instead of its intrinsic math operators.

[Boerseun]

Thanks, Craig - pretty good info there.

 

But...

 

Okay, I'm not into coding primes and encryption professionally, coding little applets and such is just a hobby of mine. So I'm not in too much of a rush to get it done.

 

Basically, I just want to understand the quickest way of determining a prime algorythmically.

 

Now - as far as I see it, for big numbers, the primes are few and far between. You can, of course, select an arbitrary size (say, 14 to 18 digits) but that'll yield a heck of a lot of numbers, and very few primes. So you're going to have to throw your computer into a loop to check all the numbers (obviously less the even numbers etc., whatever you add to your mask).

 

I suppose people have been checking and comparing primes for aeons to see if there's some logical progression of primes, without success - they seem to be random. Otherwise you could have 'predicted' a likely set of a few thousand numbers and only tested for them.

 

Anyhow - it still seems to be a bit clunky and bulky. But if the distribution of primes arer random, there's probably no other way.

 

But I suppose the amazing thing is that there are primes of that size at all...