## "wriggly" pseudoprime puzzle

Expand Messages
• ... More impressively, here is one with a 3414th root of unity: p = 43334121400711; a = 483020123189; print(znorder(Mod(a,p))); 3414 ... since the gcd extracts
Message 1 of 50 , Sep 3, 2010

> Here is an example with a 42nd root of unity:

More impressively, here is one with a 3414th root of unity:

p = 43334121400711;
a = 483020123189;
print(znorder(Mod(a,p)));
3414

It fools these tests:

> 1. p is an odd positive integer,
> 2. a is an integer with kronecker(a,p) = -1,
> 3. a^((p-1)/2) = -1 mod p,
> 5. Mod(1+x,x^2-a)^p = 1-x mod p,

but not my gremlin-trap:

> 4. gcd(a^6-1,p) = 1,

since the gcd extracts a factor:

print(gcd(a^6-1,p));
384634897

Puzzle: Find a pseudoprime, p,
with a false witness, a,
that fools (1), (2), (3), (5) and has
znorder(Mod(a,p)) > 3414.

Comment: I think it unlikely that you will also fool (4).

David
• ... [4] is meaningless, as it stands. You should write a double mod: 4. (1+x)^p = 1-x mod(x^2-a,p) ... There is no reason whatsoever to believe that [1] to [4]
Message 50 of 50 , Sep 29, 2011
"bhelmes_1" <bhelmes@...> wrote:

> 1. let a jacobi (a, p)=-1
> 2. let a^(p-1)/2 = -1 mod p
> 3. a^6 =/= 1 mod p
> 4. (1+sqrt (a))^p = 1-sqrt (a)

[4] is meaningless, as it stands.
You should write a double mod:

4. (1+x)^p = 1-x mod(x^2-a,p)

> 1. Is it possible that there are other exceptions

There is no reason whatsoever to believe that
[1] to [4] establish that p is prime. Morevoer,
some folk believe that, for every epsilon > 0,
the number of pseudoprimes less than x may
exceed x^(1-epsilon), for /sufficiently/ large x.

> 2....
> there is a cyclic order ...

> 3....
> there is a cyclic order ...

The group of units (Z/nZ)* is /not/ cyclic
if n has at least two distinct odd prime fators.

David
Your message has been successfully submitted and would be delivered to recipients shortly.