Re: More primality testing (was: Elementary group theory: Proof of Fermat-Maas ...)

In article <rem-2007jan28-004@xxxxxxxxx> rem642b@xxxxxxxxx (robert maas, see http://tinyurl.com/uh3t) writes:
From: "*** T. Winter" <***.Win...@xxxxxx>
- The chance that p-1 has a factor of trialDivisor is expected to
be 1/trialDivisor. Likewise the chance that p has a factor of
trialDivisor is expected to be 1/trialDivisor. Likewise the
chance that p+1 has a factor of trialDivisor is expected to be
1/trialDivisor. So the value you can expect to get by a single
trial division is 3/trialDivisor, 1.5 times as much as if you
were only testing p having a factor and collecting factors of p-1.

Eh?

Which part of that don't you understand?

My "Eh?" was about the relevance. In the program I use I do trial division
until some limit and during the process I collect factors of p-1 and p+1
that come out useful later. So if I only collect factors of p-1 in the
process, I forget the information about p+1 that can come in useful. So
to get those factors of p+1, I have to redo the whole process.

....
So a single triple-trial-division on the
average is worth only a small bit more than 1/trialDivisor, not
3/trialDivisor as I so generously granted you.

You are wrong. It gives information that can be used later in
primality proving.

If the first
random-Fermat test shows you likely have a prime, the number
probably really is prime, and another twenty random-Fermat tests
won't have a Sahara-snowball's chance of telling you differently,
so they'd be a waste. So when your trial divisors have gotten so
large that the expected value of one more test divided by the cost
is less than the value/cost ratio for a Fermat test, then you
should stop doing trial divisions and do that one Fermat test
immediately. If that one Fermat test shows base**(p-1)=1, then you
have two options to proceed, gather more factors of p-1 and p+1
until you can run a efficient prime-proof method, or use that one
base to try to get too may roots of something thereby proving p is
not prime. Depending on how many small factors p-1 and p+1 have
that you can find cheaply, you may choose to do the too-many-roots
test before proceeding to look for really-hard-to-find factors of
p-1 and p+1. I haven't worked out the cost/benefit comparisons for
those paths yet.

No, because you have not worked out how primality proving actually works
currently.

- The whole purpose of this primality-test is to filter non-primes
out from randomly generated numbers.
Wrong. It is also used to gather information about small divisors of
p-1 and p+1. Moreover, this is a generic primality proving algorithm.
Whether the number is randomly generated or not has no influence.

You obviously didn't understand what I said there. Here's a
hierarchy of your task-goals:
-1- Produce a new random large prime for some purpose such as RSA.

That was not one of the task goals of the program.

-2- Pick a random large number, test whether it's prime or not,
repeat until you get a prime, i.e. filter primes from
non-primes among the stream of randomly-generated numbers.

That was not one of the task goals of the program.

-3- Conduct trial divisions, Fermat test(s), too-many-roots tests,
collection of small factors of p-1 ad p+1, and advaced
primality test which uses those small factors.

That was not one of the task goals of the program.

I only did show that the program could be used quite effectively in the
finding of a random prime, and so reliance on pseudo primes was not
needed.

Alternately:
-1- Win some prize.
-2- Test one or published numbers as to whether they are prime or
not, i.e. filter primes from non-primes among the set of of
published numbers.
-3- Same as before.

As far as I know there are no prizes for proving a number prime.
There are prizes for the factorisation of numbers, that is something
different. We have received at leased one RSA prize, but I do not
know where the cheque is; probably never cashed. Factorisation is
difficult, proving a number prime or composite is much less difficult.

There's no reason on Earth to perform -3- except in support of -2-.
The whole purpose, as I said, of little parts of -3-, such as
collecting factors of p-1 and p+1, is in support of -2-, proving
whether each p is prime or not, thereby filtering the primes from
the non-primes. I am not wrong there!!

You are, because you do not know how the method works.

And as you have use of the small divisors of both p-1 and p+1
later, it comes in pretty usefil.

Maybe you do, and maybe you don't. If both p-1 and p+1 actually do
have several small divisors, then you luck out. But if they don't,
all that effort was wasted. You're no closer to proving primality
or non-primality than Edison was toward a practical light bulb when
he eliminated one possible material for use as light-bulb filament.

Right, if you do not find a few the remaining part is harder.

Before you do that one Fermat test, the chance of such a test
showing conclusively that your number is not prime is basically the
density of composite numbers among odd numbers in the ballpark of
integers you're exploring. That chance is considerably greater than
50% for large numbers such as 120 digits. By comparison, the chance
a single trial division will tell you *anything* useful (other than
one more idea didn't work, one more filament burns out too
quickly), gets infinitesimally small as the trial divisor gets
arbitrarily large.

Indeed. But a Fermat test for the kind of numbers we speak of takes
roughly the same time as the trial divisions. And that time is marginal
with respect to the overall time in primality proving. On the other
hand, when you find a prime by trial division you are *much* faster
than with a single Fermat test.

It was specifically designed to prove whether some (large)
numbers in the Cunningham tables for which it was not known
whether they were composite or not, to give a proof of either.

Gabriel Cunningham who posted to sci.math recently, or somebody else?
According to Google Groups, the last use of the phrase
"Cunningham tables" prior to your use here was way back in mid-2004.
That apparently dealt with factors of cyclotomic numbers.
Is that what you're talking about? Are those tables accessible online?
Back in late 2003 you yourself cited them as "a list of factors of 2^n,
etc.". Is that correct?

I think not. I would not have made such an egregious error.

In early 2000 there was a link to:
<http://homes.cerias.purdue.edu/~ssw/cun/index.html>
which dealt exclusively with a**n +/- 1 for a in [2,12] and n large odd.
Is that what you're talking about?
Those are special numbers which in general are easier to factor
than random numbers of similar size.

You think so. But factorisation was not the question. The question was
whether remaining factors were prime or not.

When doing my generation of a random prime of 120 digits, I
scanned over 294 candidates.

When you say "scanned", I assume mean classify, for example some
were obviously non-prime by one test or another, the very last one
was provably prime, and the rest fell into other categories, such
as probably prime but too hard to prove prime?

Wrong. The very last one was provably prime, the others were provably
not prime. For numbers of that size the program states either that the
number is prime or that it is not prime. No in-between.

In 256 cases the number did not survive trial division, the
largest divisor found was 55717. The time needed for this one was
0.048 seconds. A pseudo-prime test uses about 0.046

By "pseudo-prime test" you mean a single random-base Fermat test?

Right.

Or something more complicated? Or something less complicated (such
as Fermat with fixed base such as 2, which I consider inferior to
random base)?

Everyone knows it is.

So you're saying for that one case that consumed a lot of time
doing trial division, it wouldn't have helped to do a Fermat test
instead, or whatever you mean by "pseudo-prime test", because a
"pseudo-prime test" would have taken essentially the same length of
time to achieve the same result, category=nonprime?

Indeed. But I do not think that 0.048 seconds is a lot of time.

Also you're saying that for all the other cases where trial
division found non-primeness, that method was significantly faster
than a "pseudo-prime test" would have been, so you made the right
choice running trial division instead?

Again, indeed.

You need to balance the 255 cases where trial division produced
non-prime result in much less time than a single "pseudo-prime
test" would have, against the other cases where trial division
*never* produced any definitive result despite considerably more
investment than a single "pseudo-prime test", where a single
"pseudo-prime test" would have cliched the matter already.

Total: 294 number tested. When I had started with Fermat on all of
them (without trial division) the first 293 would have taken about
13 seconds. The total time to find the prime is about 15 seconds,
of which about 9.5 seconds is used in the proving prime of the last
one.

Which is more than twice the cost of a single "pseudo-prime test".
How many candidates went all that way, to no avail, then
immediately tested non-prime when you finally switched to the
"pseudo-prime test"?

You can do calculations? 256 of the 294 candidates did not survive
trial divisions. So, how many are left? 294 - 256 - 1 = 37.

One candidate did also survive the pseudo prime test.

The one candidate you finally proved was prime, or another earlier
that you couldn't prove prime so you set aside, where the one you
really did prove prime doesn't count as a "candidate" in the above
sentence?

Try some reading. One candidate did also survive the pseudo prime test.
There was (out of the 294) only one candidate that did survive trial
division and Fermat. And that number was proven prime.

In that case the remaining factor was:
28988632716339269019731982692336680940408646961327424290384644373248\
10095465363511659807695206555579326234594280889

Remaining factor of what???

You did read the original article? This was in response to your:
If the remaining factor of (p-1) is prime, the you can run
the Fermat-Maas test immediately.

So why the question?

There's no remaining factor involved. The whole number p is still
unresolved.

Retain context. The remaining factor of p-1, which should have been
clear when you had read the article, rather than skimming over it.

Or do you mean p-1 or p+1, which had lots of small factors pulled
out along the way, leaving one remaining factor each? That's two
(2) remaining factors, one for p-1 and another for p+1. So what
does the phrase "the remaining factor" mean???

What you meant when you wrote it.

but I do not know factors at all.

You're talking about this being a factor of p-1 or p+1 ??
What is the p you're testing at this point?

Can't you read? It is the remaining factor of p-1 after weeding out small
primes.

If we look again at p-1, the remaining factor is
33243844858187235114371539784789771720652118074916770975211748134458\
83137001563660160329925695591260695223158579

OK, here you are clear you're talking about trial divisors of p-1,
and after pulling them all out (up to your limit of 100,000
presumably), this is what's left, an unresolved divisor of p-1?

Ah, you are starting to understand it.

We continue and we go through the series of composites:
13056258290074320601041371370980194690382577203250636625250077815748\
5002631433652508064171145062888252895419

29174470244018149817938387800452992529357285287780206074589748695273\
6045258211932067253940299

40338452724160620945672877478592658134116616501100509764506278218329\
6801574809618427

27373762871988263972343266933098100494795071228801949773764393453563\
69246777

80482074786671742403922454443758320516759348658171461568092745453237

Hmm, those are getting progressively shorter. I thought maybe you
had extended trial division to larger divisors, and those were the
unresolved quotients after each new divisor was pulled out. But I
checked, and none of those is a factor of the previous, in fact
each is relatively prime to its predecessor. So I have no idea
where you're getting those progressively smaller numbers from.

Pray, some reading comprehension. I started with some p, named the remaining
factor q of p-1, continued with that and named the remaining factor r of q-1,
and continued this way.

and finally the prime
1076366484602147092546975531532636822831532507598719595143807113

Indeed that passes random-Fermat test. But it's nowhere near 120
digits, so I don't see why you care about proving it's prime.

Darn, your are reading impaired, or what?

(setq p 1076366484602147092546975531532636822831532507598719595143807113)
(qf (+ -1 p) 100000)
(2 2 2 7 17 79 2341 5209 1173654736113133450139465346242456488234770875081581)
....
Summary, for
p=1076366484602147092546975531532636822831532507598719595143807113,
we definitely don't have a complete factorization of p-1, but we
probably do have a complete factorization of p+1, but can't prove
it's complete so can't use it in proof that p is prime, and
together the two partial factorizations aren't enough to run the
super-dooper prime-proof, right?

The primality proving program proves it prime within less than a second.

So I guess you just have to chuck
that likely-prime as unprovable per present technology

Wrong, it can be proven prime by the present technology. The present
technology is far beyond using complete factorisations of either p-1
or p+1.

But try to prove it prime. The original number is:
1234567890123456789012345678901234567890123456789012345678901234567890\
12345678901234567890123456789012345678901234500733

OK, now here you *are* starting from a fixed point and working
upward until you get a provable prime.
(setq p 123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234500733)
(setq q 1076366484602147092546975531532636822831532507598719595143807113)
;Both pass Fermat test.
(gcd (+ -1 p) q) ;1
(gcd (+ 1 p) q) ;1
I have no idea how, starting from p1, doing trial division of p p-1
and p+1, you somehow end up with q.
(qf (+ -1 p) 100000)
(2 2 3 3 7 13 13
2898863271633926901973198269233668094040864696132742429038464437324810095465363511659807695206555579326234594280889)

You did not see that that number is precisely the number I quoted as the
first large number above?

;Spent another half minute there, totally wasted, no new factor.

So you did spend more than half a minute on that number, while the program
I am using (technology of about 1985) proves it prime in 9.5 seconds.

The quadratic sieve is an extremely expensive way to prove a
number prime.

Your reading comprehension is awful!

I can reciprocate this.

But you want to *prove*
it's prime using the Fermat-Maas test.

The Fermat-Maas test is not the best way to prove a number prime.

But the above large number takes only about 9 seconds to prove prime on
this fairly slow Sun. So why should I punt?

I didn't say to punt if you *can* prove it prime in such a short time.
I said to punt if neither p-1 nor p+1 can be resolved enough to
prove p prime in a reasonable amount of time.

But neither p-1 nor p+1 can be resolved enough, as you just did show
above. To prove a number prime does not require this. About 9 seconds
is the time it takes on this Sun for about every number of this size.

You should not give your customers two primes. You should give your
customer the product of two primes and two exponents, one of them
must be secret.

If you give your customers the product of two primes, and two
complementary primes, i.e. (a**r)**s = a mod p*q for all a, then
it's trivial to compute p and/or q, so you *have* in effect given
them both p and q.

Most customers will not be interested in doing those calculations.

If your customer leaks out the secret key, or computes p and/or q
and leaks that out, your customer is stupid.

Indeed. If, in cryptography, you leak out your secret key, you are
extremely stupid. And it does not matter what cryptographical method
you use. So what is the point?
--
*** t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~***/
.

Quantcast