Browse Groups

• ... 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
View Source

> 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
View Source
"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.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.