Re: primality


"Ertugrul Soeylemez" <do-not-spam-me@xxxxxxxx> wrote in message
news:f09rs1$eu3$02$2@xxxxxxxxxxxxxxxxxxxx

I really don't understand this. Is an algorithm to find twin primes
faster than an algorithm to find random primes?

no it isn't because a random prime only needs to be tested for primality
once. a twin prime has to test for primality of both numbers as not all
primes are twin primes. but that is really not the point i have been trying
to make at all.

in this example the initial state is a prime. it is used as a primative as
part of the encryption of block one. a second number is generated and tested
for primality, the test fails, a new number is randomly generated and tested
for primality. the test again fails, a third random number is generated and
tested for primality and it is a prime, so the third randomly generated
number is used as a primative for the second block of the ciphertext. the
more primality tests for each N the larger the overhead for the whole
system. this is only as predictable as the RNG that is used to generate each
N.

in the second example the initial state is also a prime and the next N is
calculated via a polynomial, i'll use the one out of my algorithm.

R = N mod 256
N = (K1 Xor K2)³ * 128 Xor (N Mod R) Xor P
test if N is an odd number

in the second example only one prime is randomly generated, every N after
the first is not necessarily a prime and is dependant on the previous value
of N.


.

Relevant Pages

  • Re: EFFICIENCY: PRIME TEST vs PRIME GENERATOR
    ... > Let's suppose we have an algorithm that will take a positive ... > For example, the USUAL test runs on odd numbers, checking for primality. ... > The time it takes to prove one such number is either composite or prime is ... > you DON'T use every partition, you might require very large exponents. ...
    (sci.math)
  • Diminished Radix parameters for DSA
    ... Algorithm Standard parameters the other day. ... bother checking p or q for primality. ... Greg Rose ...
    (sci.crypt)
  • Re: Prime Candidates
    ... >it would be nice to have a way to avoid generation of as ... an algorithm to find all primes in a given range from prime ... The least integers needed in that range to test for their primality! ... to start the initial summing process. ...
    (sci.math)
  • Re: PKI: the end
    ... the published deterministic polynomial algorithm ... The usual primality test is Rabin-Miller, with a fixed failure ... number is prime with probability at least 1-2^. ...
    (sci.crypt)
Loading