Subj : Re: Suggestions for double-hashing scheme
To   : comp.programming
From : rem642b
Date : Tue Jul 26 2005 07:06 pm

> From: websnarf@gmail.com
> > > If the algorithm is over my head, then chances are, that there is a
> > > fairly small audience who will be able to understand it.  So, who's
> > > going to be able to audit the code?
> > The math is fairly trivial. [...]
> The math for a *probabilistic method* that you describe is trivial.

I never described any probabilistic method, at least not in the sense
of getting a probability that something is prime. The only
(pseudo-)random numbers used in my method are to generate the synthetic
product of primes that equal (p-1)/2. Once that number is generated,
it's absolutely determined whether p is prime or not, although the
running time of the algorithm is probabilistic. For example, at the
point where there's a single outstanding prime factor of 3 not yet
knocked out of the possible variation in size of the multiplicative
group, i.e. the multiplicative group might be of size (p-1)/2 if p is
prime, or alternately it might be of size (p-1)/6 if p is not prime,
there's 2/3 chance it'll be resolved at the next step and 1/3 chance it
won't be resolved and need more step(s) before knocking it out.

> the Miller-Rabin method just pulls out powers of two from N-1, and
> recursively performs difference of squares factoring on (A**(N-1) - 1).

Why even bother?? Do you understand the difference between these two
different tasks?
(1) Some stranger gives you a large number, doesn't give you any idea
where it came from, and you must decide whether it's prime or not.
(2) Some stranger gives you a *range* of numbers, such as all fifty
digit numbers whose high-order digits are your telephone number, and
all you have to do is synthesize some number within that range that is
prime.

I'm talking about task 2. That's what my algorithm is for.
You seem to have gotten confused and are talking about task 1.

> I am not sure what guarantees your algorithm provides, and I worry
> about the real running time, since you need to start with complete
> factorizations of N-1, which may or may not be fast.

You are thinking ass backwards! It's totally stupid to multiply a bunch
of numbers together to get a large composite number, then forget what
numbers you started with and try to reconstruct them by factoring the
large composite number. The trick fo my method is the ***remember***
what numbers you multiplied together long enough to use them to
***prove*** the number you have (p = 2*prod+1) is truly prime.

Remembering what numbers you started with takes n units of memory and
zero units of time, right? So what's your gripe about whether that is
fast or not? Of course it's fast! It's instant!! It's already!!

> I was referring to *deterministic* methods which are polynomial.

That's much slower than my method.

> you *can* get a handful of 64 bit primes offline using just naive
> division testing, but its still very annoying -- your choice is to
> trust someone's precomputed numbers, or go through the pain of
> reproducing them yourself.

My algorithm generates all the small primes it needs from first
principles, i.e. anything between p and p**2 which isn't divisible by
any prime from 2 to p must be prime itself. It also generates all the
intermediate-sized primes it needs on an as-needed JIT basis, using the
main algorithm recursively. (The actual software I wrote more than 20
years ago was sloppy: Instead of generating primes that multplied to
yield (p-1)/2, it merely multiplied together a bunch of medium-sized
random numbers after checking each such number to see whether it was
prime or easily factorizable, discarding any number that was neither,
and appending all the factorizations of those numbers to use in the
Fermat knock-out-factor test.) There's no pain, wither with my old hack
way to synthesize the product, or with my new algorithm.

In any case, the question at hand is not whether the algorithm to
synthesize the large primes is understandable, but rather whether the
mathematical proof of primeness that it constructs is understandable.
If I were to show you a list of small to medium numbers q[], that I
allege to each be prime, and for all the small ones I merely ask you to
check yourself if you don't believe me, and for each the non-small q[i]
I present the factorization of q[i]-1 and a mathematical proof of
primeness based on that factorization, and then for the one big prime p
I likewise present a mathematical proof of primeness based on the
factorization of p-1 = 2*q[0]*q[1]*q[2]*...*q[k], how hard would it be
for anyone to understand my proofs? In each case I simply demonstrate a
specific number b such that I prove that the order of the
multiplicative group generated by b is a factor of p-1, because
b**(p-1)=1 mod p, but the order of that group is not a factor of
(p-1)/q where q is any prime factor of p-1, because b**((p-1)/q) != 1
mod p, thereby showing the order of the cyclic multiplicative group
generated by b is exactly p-1. What's hard to understand about that?

By the way, Java has built-in API support for computing the residue of
b**(p-1) etc. modulo p, for example:
  http://java.sun.com/j2se/1.3/docs/api/java/math/BigInteger.html
    #modPow(java.math.BigInteger, java.math.BigInteger)
So anyone with access to Java can easily write a trivial program to
check any "proof" I claim to see if it's true. (If I claim a particular
residue is 1 or is not 1, you plug my numbers into your Java program
and see if my claim is correct.)

.