flat assembler
Message board for the users of flat assembler.
Index
> Main > primes generator 
Author 

donkey7
where can I get it?
i will write an RSA cipher program, and I need this.  sorry for bad english _________________ Keep coding! 

27 May 2005, 20:28 

donkey7
so, how the primes are generated in generalpurpose ciphering programs???
they must have some optimized algorithm! 

27 May 2005, 20:45 

r22
You could have a large array of prime numbers that are already verified as primes and select them randomly using a random index to the array.
I have no clue how much space an array of all the primes from 1  4.29billion would take up. The following formulas may help you code an algorithm to check for primality. http://uucode.com/obf/dalbec/alg.html Code: 3. Strong ProbablePrimality and a Practical Test A better way to make the Fermat test more accurate is to write n1 = 2sd where d is odd and s is nonnegative: n is a strong probableprime base a (an aSPRP) if either ad = 1 (mod n) or (ad)2r = 1 (mod n) for some nonnegative r less than s. Again all integers n > 1 which fail this test are composite; integers that pass it might be prime. The smallest odd composite SPRPs are the following. 2047 = 23.89 is a 2SPRP, 121 = 11.11 is a 3SPRP, 781 = 11.71 is a 5SPRP and, 25 = 5.5 is a 7SPRP. A test based on these results is quite fast, especially when combined with trial division by the first few primes. Individually these tests are still weak (and again there are infinitely many aSPRP's for every base a>1, but we can combine these individual tests to make powerful tests for small integers n>1: If n < 1,373,653 is a both 2 and 3SPRP, then n is prime. If n < 25,326,001 is a 2, 3 and 5SPRP, then n is prime. If n < 25,000,000,000 is a 2, 3, 5 and 7SPRP, then either n = 3,215,031,751 or n is prime. (This is actually true for n < 118,670,087,467.) If n < 2,152,302,898,747 is a 2, 3, 5, 7 and 11SPRP, then n is prime. If n < 3,474,749,660,383 is a 2, 3, 5, 7, 11 and 13SPRP, then n is prime. If n < 341,550,071,728,321 is a 2, 3, 5, 7, 11, 13 and 17SPRP, then n is prime. The first three of these are due to Pomerance, Selfridge and Wagstaff, the parenthetical remark and all others are due to Jaeschke. If n < 9,080,191 is a both 31 and 73SPRP, then n is prime. If n < 4,759,123,141 is a 2, 7 and 61SPRP, then n is prime. If n < 1,000,000,000,000 is a 2, 13, 23, and 1662803SPRP, then n is prime. Here is the way we usually use the above results to make a quick primality test: start by dividing by the first few primes (say those below 257); then perform strong primality tests base 2, 3, ... until one of the criteria above is met. For example, if n < 25,326,001 we need only check bases 2, 3 and 5. This is much faster than trial division (because someone else has already done much of the work), but will only work for small numbers (n < 341,550,071,728,321 with the data above). Finally, there is a fair amount more that could (and should) be said. We could discuss Euler pseudoprimes and their relationship with SPRPs. Or we could switch to the "plus side" and discuss Lucas pseudoprimes, or Fibonacci pseudoprimes, or the important combined tests... but that would take a chapter of a bookand it has already been well written by Ribenboim. Let us end this section with one last result: Millers Test: If the generalized Riemann hypothesis is true, then if n is an aSPRP for all integers a with 1 < a < 2(log n)2, then n is prime. The generalized Riemann hypothesis is far too complicated for us to explain herebut should it be proven, then we would have a very simple primality test. Until it is proven, we can at least expect that if n is composite, we should be able to find an a that shows it is composite (a witness) without searching "too" long. (Most surveys cover Miller's test; the improvable constant 2 is do to Bach) 

28 May 2005, 00:22 

marciano
r22 wrote: You could have a large array of prime numbers that are already verified as primes and select them randomly using a random index to the array. Using the KAnal plugin for PEiD, I have found that some apps include lists of primes. For example, list of the first 200 prime numbers. 

28 May 2005, 03:00 

YONG
Try this link:
http://www.utm.edu/research/primes/index.html  Includes the 5000 largest known primes, lists of 300digit primes, etc. YONG 

28 May 2005, 07:26 

Reverend
There are some testes for prime numbers eg. RabinMiller's (the most popular), Fermat's, but all of them won't telly you for 100% percent. But after about 100 positive tests you can assume the number is prime. And that's how all "primegenerators" work. Google for RabinMiller and Fermat's prime test for more info
Quote: Using the KAnal plugin for PEiD, I have found that some apps include lists of primes. I think this list of primes is for another use. Because if we have for example such list of primes: 2, 3, 5, 7, 11, 13 we can get the highest one and calcualte it's square. 13*13 = 169. So using this array we can check every number form 2 to 169 for primarity. We just have to divide that number by every elemnt of our array, and if there's no modulo the number is prime. If we have an array od 200 number we can calculate of course mouch more. For better imagination of this idea check this: Code: array = 2, 3, 5, 7, 11, 13 max = 13*13 = 169 random_number = 143 143 mod 2 = 1 143 mod 3 = 2 143 mod 5 = 3 143 mod 7 = 3 143 mod 11 = 0 !!! So the number is not prime, as one of it's base factors is 11 another_random_numer = 139 139 mod 2 = 1 139 mod 3 = 1 139 mod 5 = 4 139 mod 7 = 6 139 mod 11 = 7 139 mod 13 = 9 This number is prime as it has no factors in our array and is in (2, 169) 

28 May 2005, 10:27 

Matrix
i found this site recently, it might interest you
GIMPS Prime Search index 

28 May 2005, 12:24 

donkey7
are any primes in openpgp?
how they ciphers data (algorithms)? 

28 May 2005, 17:49 

donkey7
reverend: i already know your algorithm.
see: www.ilo.tarnow.pl (polish) there are some algos but there are no generators 

28 May 2005, 17:52 

Reverend
donkey7 wrote: see: www.ilo.tarnow.pl (polish) there are some algos but there are no generators 

28 May 2005, 19:29 

YONG
Quote:
The correct noun is primality. YONG 

29 May 2005, 07:05 

donkey7
heh, i think there is no way to generate big primes fast enough. so, have anyone an array with say 2048 bit integers???


03 Jun 2005, 18:34 

YONG
This quote is from the link below:
Quote:
http://www.utm.edu/research/primes/prove/prove1.html Hope that this would help a bit. YONG 

04 Jun 2005, 08:14 

donkey7
some question:
how do the usual RSA programs ciphers data? do they expand the data? how do they divide the data into portions and saves the ciphered stream i know the formulas, but i don't know exactly how to implement this? i saw program that ciphers only one symbol per time. 

06 Jun 2005, 18:31 

YONG
Perhaps you should take a serious look at some of the links of RSA Laboratories:
http://www.rsasecurity.com/rsalabs/node.asp?id=2146 YONG 

07 Jun 2005, 06:54 

< Last Thread  Next Thread > 
Forum Rules:

Copyright © 19992020, Tomasz Grysztar. Also on GitHub, YouTube, Twitter.
Website powered by rwasa.