4 ms·
>I don't know the precise odds but we can infer that it's roughly on the order of 2^-32 (for some definition of trivial) The chance is way, way, WAY larger tha
by hifromwork 2y ago
>I don't know the precise odds but we can infer that it's roughly on the order of 2^-32 (for some definition of trivial)
The chance is way, way, WAY larger than 2*-32. Consider the following code:
primes = [2, 3, 5, 7, ..., 499]
def miller_rabin(n, k): ... # your fast primarity test of choice
def is_prime_trivial(n):
for p in primes:
while n % p == 0:
n //= p
if n == 1:
return True
return miller_rabin(n, 20)
It fully factors a random 2048bit integer in around 100 tries, for me.