Dirty Primes
 

I have written a generator of Dirty Technical Primes.
[url]http://persicum.front.ru/purgen_01.zip[/url]
In principle, it uses FFT - but jet very slow =(((.
May I ask some questions?

1) Is there kind of "middle" test, much slower than trial division on 3,5,7 but still much faster then Rabin??? I want to embed it before Rabin-test.

2) I use padding of DOUBLES with 16-bit integers (it's easier than 24 and especially 19-20 bit). At what length of long numbers the FFT-mult can glitch due to rounding errors?

The program was renewed:
[url]http://persicum.front.ru/purgen_02.zip[/url]

It works :banana: , but maybe slower than it would be.
Where can I download a ready-to-use DLL of FFT via SSE2 and with Delphi interface?

Closest I could find.

Delphi
[url]http://www-rab.larc.nasa.gov/nmp/nmpIndex.htm[/url] Lots of links
[url]http://www.simdesign.nl/fft.html[/url] fft library
[url]http://www.aho.ch/fft/[/url] fft library
[url]http://www.tommesani.com/Exentia.html[/url] library for SIMD x87,3DNow,SSE/SSE2

C and Fortran
[url]http://www.fftw.org/[/url] fft with SSE2
[url]http://www.fftw.org/benchfft/[/url]
[url]http://www.ece.cmu.edu/%7espiral/software.html[/url]
[url]http://www.ece.cmu.edu/%7espiral/fft.html[/url]
[url]http://www.ece.cmu.edu/~pueschel/publications.html#sse[/url]

Version 0.3 has been released!!! But still slow since w/o any SSE/SSE2 =(((
Generalized-Compound-Holey Mersenne Numbers are now supported!!!
My first experience is:

2^32768 - 2^8128 - 2^4832 + 2^4640 + 2^4448 - 2^3968 + 1
2^16384 - 2^2752 + 2^1440 + 2^1312 + 2^128 - 1
2^2048 - 2^768 + 2^512 - 2^192 - 2^64 - 2^32 + 1
2^1024 - 2^128 - 2^96 + 2^64 + 2^32 + 1 - beauty =)))


2^16384 - 2^6432 + 2^2272 + 1
2^8192 - 2^1824 - 1
2^8192 - 2^576 + 2^320 + 1
2^4096 - 2^160 + 2^96 + 1
2^2048 - 2^1472 + 2^1152 + 1
2^2048 - 2^448 + 2^192 + 1
2^1536 - 2^864 + 2^64 + 1
2^1024 - 2^512 + 2^128 - 2^64 - 1
2^768 - 2^96 - 1
2^512 - 2^288 + 1
2^512 - 2^32 - 1 (Twins !!!)
2^192 - 2^64 - 1

2^4095 + 78FD6C5Fh
2^1023 + 63CC3D3Dh
2^4096 - 2^2048 - 2^2016 + 2^704 - 2^672 + 2^288 + 1
2^4096 - 2^1024 - 2^192 - 2^96 + 2^32 - 1
2^2048 - 2^1024 - 2^512 - 2^160 + 1
2^2048 - 2^1024 - 2^128 + 2^64 - 1
2^2048 - 2^512 - 2^224 + 2^192 + 2^32 + 1
2^1536 - 2^224 - 2^128 + 2^64 - 1
2^1024 - 2^800 + 2^64 + 2^32 - 1
2^768 - 2^512 - 2^96 + 2^64 + 1
2^512 - 2^256 + 2^192 - 2^128 - 1
2^192 - 2^160 - 2^96 + 2^64 + 2^32 + 1
(2^2048 - 2^1984 + 2^1152 - 2^608 - 2^512 + 2^480 + 2^448 - 2^384 + 2^288 + 2^224 + 2^160 - 2^128 - 2^96 - 2^64 + 1) :unsure:

Dirty Primes
 

I am curious.

How are you proving these numbers prime?

For some of them it is easy, e.g. N = 2^512 - 2^288 + 1 because
we know all the factors of N-1 up to (and beyond) N^.3. However,
the method of proof for e.g.

2^32768 - 2^8128 - 2^4832 + 2^4640 + 2^4448 - 2^3968 + 1

is unclear. Or are you just testing that they are probably primes?

At the moment, I dont' know is there a LL-like fast deterministic test for compound-mersenne-numbers. That's why I use common probabilistic Rabin-Miller Test. This is not strict, but all of this numbers are primes of course.
The probability for N to be prime is 1/ln(N), The probability to be pseudoprime is 1/N(2/3). So the probability 2^32768... is not prime but pseudoprime is zero-zero modulo zero fucking zero... Exactly 2^(-20000)*2^(-10). You can test them in Mathematica 5.0 PrimeQ[], deterministic LL-common slow test for all primes (dont' confuse with LL-test for mersenne much spoken about here)

[QUOTE=Cyclamen Persicum]At the moment, I dont' know is there a LL-like fast deterministic test for compound-mersenne-numbers. That's why I use common probabilistic Rabin-Miller Test. This is not strict, but all of this numbers are primes of course.
The probability for N to be prime is 1/ln(N), The probability to be pseudoprime is 1/N(2/3). So the probability 2^32768... is not prime but pseudoprime is zero-zero modulo zero fucking zero... Exactly 2^(-20000)*2^(-10). You can test them in Mathematica 5.0 PrimeQ[], deterministic LL-common slow test for all primes (dont' confuse with LL-test for mersenne much spoken about here)[/QUOTE]
Uh-oh. :ermm:

Bob tends to like mathematically precise statements when people are talking about mathematics. I tend to like preemptive retaliation, so here goes. :wink:

You're correct that the likelihood of the larger numbers being composite is extremely small, assuming that the PRP test ran correctly, but it is [B]not[/B] precisely zero.

There are philosphical arguments as to whether any computation can prove primality because it's possible that a hardware or software error may have corrupted part of the computation. Suggesting that repeating a computation on different hardware using a different implementation of a different algorithm guards against such error is equally fallacious. It's possible, though increasingly unlikely, that all such repeated runs will produce the same erroneous answer through corruption of part of the computation.

Proof can be a tricky concept in the real world.

Your statement about probabilities and your numerical estimates are very wrong, too. I'll leave it as a research project to find out how, why, how to state the problem precisely and how to find a better estimate.

Paul

Dirty Primes
 

May I suggest that the original poster

(1) Refrain from profanity while posting.
(2) Proofread his post before submitting. The Expression 1/N(2/3) is obviously
not what was intended. [and it is likely that what was intended is wrong]
(3) Be less than dogmatic about a subject area in which he is less than
expert.
(4) Read the following:

Damgaard, Landrock, & Pomerance
Average Case Bounds for the Strong Probable Prime Test
Math. Comp. vol 61 #203

P. Mihailescu
Cyclotomy of Rings & Primality Testing
dissertation, Swiss Fed. Inst. Technology,

D. Bressoud
Factorization & Primality Testing, Springer-Verlag Undergrad Texts in Math.


It might also be useful if he gave a definition of "generalized Mersenne prime".
Please note that ALL numbers have a binary representation. For a randomly
chosen integer, 1/2 the bits will be lit on average. The poster obviously
intends "generalized Mersenne primes" to mean integers of low Hamming weight, but there must be more to it than that. Perhaps what is also
intended is that the bits that are lit have index that is a largish power of two or small multiple of the same. Please define.

Finally, let me say that in general there will NOT be a LL-like proof for these
numbers. One needs to find a group of the right size and construct a
generator. For (sub-groups of) finite fields of index greater than 2, the rule for doing exponentiation will not be so simple as S_n = S_{n-1}^2 - 4.
Furthermore, for a group of the proper size to exist, the number, when
evaluated as a cyclotomic polynomial must be fully (or sufficiently) factored.

Another way of looking at this is to note that for Mersenne primes, the full
factorization of N+1 is known. N+1 is a cyclotomic polynomial dividing N^2 - 1. Thus, one finds a generator of the sub-group whose order is N+1 in the
finite field GF(N^2) [whose order is N^2 - 1]

Lucas-Lehmer type proofs of Mersenne Primes do not apply more generally,
because it is very rare that one can find a candidate N where a cyclotomic
polynomial in N has its value fully factored (or factored up to N^.3 via
Pomerance & Konyagin's results].

In the example I quoted, we have N = 2^512 - 2^288 +1,
and N-1 = 2^288(2^224 - 1). We can now get a complete factorization of
N-1, but it isn;'t needed. 2^288 exceeds n^(1/3) so we can user the
Brillhart-Lehmer-Selfridge methods to prove this prime (if it is).

I suggest that the poster do some background reading before
going further with this subject.

[i](1) Refrain from profanity while posting. [/i]

Oh, Bob, excuse me please, it seems you are very serious man, a PhD or even a professor...

[i](2) Proofread his post before submitting. The Expression 1/N(2/3) is obviously not what was intended. [/i]

By my troth, I tried to edit my message, but notwithstanding I'm a registered poster, I could not do this and even could not find how to do this... Why do you totally disagree with my estimation of the probability of error? The probability for N to be CarMichael Number is 1/N^(2/3), is not it? And extra-factor 2^(-10) give five rounds of Rabin Test.
.
[i](4) Read the following:[/i]
Do you think I know the difference between a ring and a field? =)))
I'm not a mathematician at all, just a coder. I'm interested in what to do to obtain a working program and looking for ready-to-use solutions and algorithms. That's why I ask clever guys how can I proof the primality of Generalized Mersenne numbers.

[i]It might also be useful if he gave a definition of "generalized Mersenne prime".[/i]

As you can see, I have created the thread "Generalized Mersenne Primes" a couple weeks ago. I hoped that Celebrated Largest Mersenne Discoverers would give me some advices how to find these numbers and what criteria I should use to sieve candidates and to proof its primality. But there is no answer so far... Generalized Mersenne Primes are widely used in cryptography due to their eminent properties:
1) modular reduction is easy and instant
2) there are enormous quantity of them for every large-enough exponent
3) they are machine-friendly and machine-word aligned.


[i]Please note that ALL numbers have a binary representation.[/i]
Yes, they have. So we can write p=Sum[c(i)*2^n(i)].
Usually one says that in case of Generalized Mersenne Prime c-vector is sparse, so only small amounts of coefficients c(i) are not equal to zero.
This is correct, but not enough. Crandall Primes 2^n+c also have almost only zeros. I think that Generalized Mersenne Prime has c(i) from the set (-1,1), the number of terms not very large (3-5), and n(i) is divisible by machine-word length (definitly, 32-bit).


[i]Finally, let me say that in general there will NOT be a LL-like proof for these numbers.[/i]
So the Rabin-Miller is the best choice? How are Generalized Mersenne Numbers obtained for cryptography purposes? MayBe, there is a LL-like proof for 2^a-2^b-1, such as 2^512-2^32-1? It has ONLY one zero in binary representation. In principle, obtaining a very large Gen.Mers.P. is peerless easier than Regular Mersenne Prime or 3*2^n-1. Unfortunately, my prog currently is about 50 times slower than Prime95 =(((. Since 99.9% of time spend for FFT, maybe in future I will attach the fastest SSE2 FFT available (namely, fftw3.dll)

[QUOTE=Cyclamen Persicum][i](1) Refrain from profanity while posting. [/i]

Oh, Bob, excuse me please, it seems you are very serious man, a PhD or even a professor...

[FONT=Courier New]===Deletions===[/FONT]

How are Generalized Mersenne Numbers obtained for cryptography purposes?
[/QUOTE]
I think that you'll find quite a few people around here have been doctored. Not all have the PhD degree. At least one has a DPhil. Not sure whether there are any DD, DMus or DLitt types around here.

Most primes used for cryptographic purposes are so small (typically a few hundred to a few thousand bits) that general purpose algorithms such as ECPP or cyclotomy are sufficient to prove primality.

Paul

Here is the top-list of dirty primes:
[url]http://www.primenumbers.net/prptop/prptop.php[/url]

2^551542+19249 probably prime