flat assembler
Message board for the users of flat assembler.
![]() |
Author |
|
donkey7 27 May 2005, 20:28
where can I get it?
i will write an RSA cipher program, and I need this. ------------------------ sorry for bad english _________________ Keep coding! |
|||
![]() |
|
donkey7 27 May 2005, 20:45
so, how the primes are generated in general-purpose ciphering programs???
they must have some optimized algorithm! |
|||
![]() |
|
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) |
|||
![]() |
|
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. |
|||
![]() |
|
YONG 28 May 2005, 07:26
Try this link:
http://www.utm.edu/research/primes/index.html - Includes the 5000 largest known primes, lists of 300-digit primes, etc. YONG |
|||
![]() |
|
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. 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) |
|||
![]() |
|
Matrix 28 May 2005, 12:24
i found this site recently, it might interest you
GIMPS Prime Search index |
|||
![]() |
|
donkey7 28 May 2005, 17:49
are any primes in openpgp?
how they ciphers data (algorithms)? |
|||
![]() |
|
donkey7 28 May 2005, 17:52
reverend: i already know your algorithm.
see: www.i-lo.tarnow.pl (polish) there are some algos but there are no generators ![]() |
|||
![]() |
|
Reverend 28 May 2005, 19:29
donkey7 wrote: see: www.i-lo.tarnow.pl (polish) there are some algos but there are no generators |
|||
![]() |
|
YONG 29 May 2005, 07:05
Quote:
The correct noun is primality. YONG |
|||
![]() |
|
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???
|
|||
![]() |
|
YONG 04 Jun 2005, 08:14
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 |
|||
![]() |
|
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. |
|||
![]() |
|
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 |
|||
![]() |
|
< Last Thread | Next Thread > |
Forum Rules:
|
Copyright © 1999-2025, Tomasz Grysztar. Also on GitHub, YouTube.
Website powered by rwasa.