flat assembler
Message board for the users of flat assembler.

Index > Main > primes generator

Author
Thread Post new topic Reply to topic
donkey7



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


------------------------
sorry for bad english

_________________
Keep coding!
Post 27 May 2005, 20:28
View user's profile Send private message Visit poster's website Reply with quote
Reverend



Joined: 24 Aug 2004
Posts: 408
Location: Poland
Reverend
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 Wink)

I guess that there is a mathmeatical proof for that

P.S (for PL useres only): Witam ziomka z Polski. FASM: Dobre bo polskie Very Happy
Post 27 May 2005, 20:34
View user's profile Send private message Visit poster's website Reply with quote
donkey7



Joined: 31 Jan 2005
Posts: 127
Location: Poland, Malopolska
donkey7
so, how the primes are generated in general-purpose ciphering programs???
they must have some optimized algorithm!
Post 27 May 2005, 20:45
View user's profile Send private message Visit poster's website Reply with quote
r22



Joined: 27 Dec 2004
Posts: 805
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 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) 
    
Post 28 May 2005, 00:22
View user's profile Send private message AIM Address Yahoo Messenger Reply with quote
marciano



Joined: 27 Feb 2005
Posts: 18
Location: Argentina
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.
Post 28 May 2005, 03:00
View user's profile Send private message Visit poster's website Reply with quote
YONG



Joined: 16 Mar 2005
Posts: 8000
Location: 22° 15' N | 114° 10' E
YONG
Try this link:

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

YONG
Post 28 May 2005, 07:26
View user's profile Send private message Visit poster's website Reply with quote
Reverend



Joined: 24 Aug 2004
Posts: 408
Location: Poland
Reverend
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)
    
Post 28 May 2005, 10:27
View user's profile Send private message Visit poster's website Reply with quote
Matrix



Joined: 04 Sep 2004
Posts: 1171
Location: Overflow
Matrix
i found this site recently, it might interest you
GIMPS Prime Search index
Post 28 May 2005, 12:24
View user's profile Send private message Visit poster's website Reply with quote
donkey7



Joined: 31 Jan 2005
Posts: 127
Location: Poland, Malopolska
donkey7
are any primes in openpgp?
how they ciphers data (algorithms)?
Post 28 May 2005, 17:49
View user's profile Send private message Visit poster's website Reply with quote
donkey7



Joined: 31 Jan 2005
Posts: 127
Location: Poland, Malopolska
donkey7
reverend: i already know your algorithm.
see: www.i-lo.tarnow.pl (polish) there are some algos but there are no generators Sad
Post 28 May 2005, 17:52
View user's profile Send private message Visit poster's website Reply with quote
Reverend



Joined: 24 Aug 2004
Posts: 408
Location: Poland
Reverend
donkey7 wrote:
see: www.i-lo.tarnow.pl (polish) there are some algos but there are no generators Sad
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 -> ???)
Post 28 May 2005, 19:29
View user's profile Send private message Visit poster's website Reply with quote
YONG



Joined: 16 Mar 2005
Posts: 8000
Location: 22° 15' N | 114° 10' E
YONG
Quote:

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

The correct noun is primality.

YONG
Post 29 May 2005, 07:05
View user's profile Send private message Visit poster's website Reply with quote
donkey7



Joined: 31 Jan 2005
Posts: 127
Location: Poland, Malopolska
donkey7
heh, i think there is no way to generate big primes fast enough. so, have anyone an array with say 2048 bit integers???
Post 03 Jun 2005, 18:34
View user's profile Send private message Visit poster's website Reply with quote
YONG



Joined: 16 Mar 2005
Posts: 8000
Location: 22° 15' N | 114° 10' E
YONG
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
Post 04 Jun 2005, 08:14
View user's profile Send private message Visit poster's website Reply with quote
donkey7



Joined: 31 Jan 2005
Posts: 127
Location: Poland, Malopolska
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.
Post 06 Jun 2005, 18:31
View user's profile Send private message Visit poster's website Reply with quote
YONG



Joined: 16 Mar 2005
Posts: 8000
Location: 22° 15' N | 114° 10' E
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
Post 07 Jun 2005, 06:54
View user's profile Send private message Visit poster's website Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar. Also on YouTube, Twitter.

Website powered by rwasa.