flat assembler
Message board for the users of flat assembler.

 Index > Main > primes generator
Author
donkey7

Joined: 31 Jan 2005
Posts: 127
Location: Poland, Malopolska
donkey7 27 May 2005, 20:28
where can I get it?
i will write an RSA cipher program, and I need this.

------------------------

_________________
Keep coding!
27 May 2005, 20:28
Reverend

Joined: 24 Aug 2004
Posts: 408
Location: Poland
Reverend 27 May 2005, 20:34
There is no way to generate a prime number. The only programs that pretend to do this are those that generate pseudorandom number and checks it if it's prime. If not, then generate another pseudorandom number, and so on. Of course, not only one test is made, because there isn't any algorithm that will check it for 100% there's always about 50% so there's 50% chance after 1 pass, 75% chance after second, and so on, but never 100% (theoretically )

I guess that there is a mathmeatical proof for that

P.S (for PL useres only): Witam ziomka z Polski. FASM: Dobre bo polskie
27 May 2005, 20:34
donkey7

Joined: 31 Jan 2005
Posts: 127
Location: Poland, Malopolska
donkey7 27 May 2005, 20:45
so, how the primes are generated in general-purpose ciphering programs???
they must have some optimized algorithm!
27 May 2005, 20:45
r22

Joined: 27 Dec 2004
Posts: 805
r22 28 May 2005, 00:22
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 Probable-Primality and a Practical Test
A better way to make the Fermat test more accurate is to write n-1 = 2sd where d is odd and s is nonnegative: n is a strong probable-prime base a (an a-SPRP) 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 2-SPRP,
121 = 11.11 is a 3-SPRP,
781 = 11.71 is a 5-SPRP and,
25 = 5.5 is a 7-SPRP.
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 a-SPRP'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 3-SPRP, then n is prime.
If n < 25,326,001 is a 2, 3 and 5-SPRP, then n is prime.
If n < 25,000,000,000 is a 2, 3, 5 and 7-SPRP, 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 11-SPRP, then n is prime.
If n < 3,474,749,660,383 is a 2, 3, 5, 7, 11 and 13-SPRP, then n is prime.
If n < 341,550,071,728,321 is a 2, 3, 5, 7, 11, 13 and 17-SPRP, 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 73-SPRP, then n is prime.
If n < 4,759,123,141 is a 2, 7 and 61-SPRP, then n is prime.
If n < 1,000,000,000,000 is a 2, 13, 23, and 1662803-SPRP, 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 book--and 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 a-SPRP 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 here--but 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

Joined: 27 Feb 2005
Posts: 18
Location: Argentina
marciano 28 May 2005, 03:00
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

Joined: 16 Mar 2005
Posts: 7997
Location: 22° 15' N | 114° 10' E
YONG 28 May 2005, 07:26

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

YONG
28 May 2005, 07:26
Reverend

Joined: 24 Aug 2004
Posts: 408
Location: Poland
Reverend 28 May 2005, 10:27
There are some testes for prime numbers eg. Rabin-Miller'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 "prime-generators" work. Google for Rabin-Miller 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.
For example, list of the first 200 prime numbers.

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

Joined: 04 Sep 2004
Posts: 1166
Location: Overflow
Matrix 28 May 2005, 12:24
i found this site recently, it might interest you
GIMPS Prime Search index
28 May 2005, 12:24
donkey7

Joined: 31 Jan 2005
Posts: 127
Location: Poland, Malopolska
donkey7 28 May 2005, 17:49
are any primes in openpgp?
how they ciphers data (algorithms)?
28 May 2005, 17:49
donkey7

Joined: 31 Jan 2005
Posts: 127
Location: Poland, Malopolska
donkey7 28 May 2005, 17:52
see: www.i-lo.tarnow.pl (polish) there are some algos but there are no generators
28 May 2005, 17:52
Reverend

Joined: 24 Aug 2004
Posts: 408
Location: Poland
Reverend 28 May 2005, 19:29
donkey7 wrote:
see: www.i-lo.tarnow.pl (polish) there are some algos but there are no generators
I told you, there is no generator! The only so-called "pseudo-generators" are based on random numbers, which are cheked for primarity (btw. is it correct word? adjective -> prime, noun -> ???)
28 May 2005, 19:29
YONG

Joined: 16 Mar 2005
Posts: 7997
Location: 22° 15' N | 114° 10' E
YONG 29 May 2005, 07:05
Quote:

btw. is it correct word? adjective -> prime, noun -> ???

The correct noun is primality.

YONG
29 May 2005, 07:05
donkey7

Joined: 31 Jan 2005
Posts: 127
Location: Poland, Malopolska
donkey7 03 Jun 2005, 18:34
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

Joined: 16 Mar 2005
Posts: 7997
Location: 22° 15' N | 114° 10' E
YONG 04 Jun 2005, 08:14
This quote is from the link below:
Quote:

Chapter Two: The quick tests for small numbers and probable primes

For very small primes we can use the Sieve of Eratosthenes or trial division. These methods are sure, and are the best methods for small numbers, but become far too time consuming before our numbers reach thirty digits.

If we are going to use our primes for "industrial" uses (e.g., for RSA encryption) we often do not need to prove they are prime. It may be enough to know that the probability they are composite is less than 0.000000000000000000000001%. In this case we can use (strong) probable primality tests.

These probable primality tests can be combined to create a very quick algorithm for proving primality for integers less than 340,000,000,000,000.

http://www.utm.edu/research/primes/prove/prove1.html

Hope that this would help a bit.

YONG
04 Jun 2005, 08:14
donkey7

Joined: 31 Jan 2005
Posts: 127
Location: Poland, Malopolska
donkey7 06 Jun 2005, 18:31
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

Joined: 16 Mar 2005
Posts: 7997
Location: 22° 15' N | 114° 10' E
YONG 07 Jun 2005, 06:54
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
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainTutorials and ExamplesDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsOS ConstructionIDE DevelopmentProjects and IdeasNon-x86 architecturesHigh Level LanguagesProgramming Language DesignCompiler Internals Other----------------FeedbackHeapTest Area

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou cannot attach files in this forumYou can download files in this forum