Tim Peters <[email protected]> added the comment:
[Steven]
> ... Try it on numbers like this:
> ...
> Q = P*(313*(P-1)+1)*(353*(P-1)+1)
>
> Q is a 397 digit Carmichael Number. Its smallest factor is P,
> which has 131 digits.
> ...
> My old and slow PC can prove that Q is a composite number,
> using pure Python, in less than six seconds.
>
> And I'm sure that a better programmer than me would be
> able to shave off some of that time.
The pure-Python Miller-Rabin code i posted in the aforementioned thread is
typically at least 100 times faster than that. But it's not deterministic.
Because it tries (pseudo)random bases, it all depends on how many it needs to
try on each run before finding a witness to that Q is composite. It usually
(at least 75% of runs) finds one on the first try.
BTW, it doesn't much matter that this is "pure Python" - for ints of this size
the bulk of the time regardless is spent in CPython's C-coded bigint
arithmetic. I expect that your code must be doing more than _just_
Miller-Rabin, and in the Q case is paying through the nose for "optimizations"
that all fail before getting to Miller-Rabin.
About the API, I can't agree to the one you propose. Different applications
have different appropriate tradeoffs between degree of certainty and time
consumed - "one size fits all" doesn't fly here.
def probably_prime(n, maxsteps=20)
supplies a _default_ instead. I don't want an API that's useful _only_ to
people who don't know what they're doing ;-)
> (By the way: for smallish numbers, under 2**64, no more than
> twelve rounds of Miller-Rabin are sufficient to
> deterministically decide whether a number is prime or not.
But only if you use a fixed set of 12 specific bases for which the claim has
been proved. "Real" Miller-Rabin picks bases at random, relying only on
properties that have been proved independent of the argument size.
[Vedran]
> Tim: Considering that congruence is _defined_ as
> x=y(mod m) :<=> m|y-x, it's
> really not so surprising. :-)
Didn't say it was ;-) Was just noting the odd coincidence that I just happened
to stumble into a real use for lcm(), not previously mentioned in this report,
while doing something else.
----------
_______________________________________
Python tracker <[email protected]>
<https://bugs.python.org/issue39479>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
