Browse Groups

• ... Comment: The gremlins can generate false witnesses for this puzzle at a rate in excess of 50 kHz, finding more than 600,000,000 in less than 3 hours. ...
Message 1 of 50 , Sep 5, 2010
View Source

> 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

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

Comment: The gremlins can generate false witnesses
for this puzzle at a rate in excess of 50 kHz,
finding more than 600,000,000 in less than 3 hours.

Hint: All of these false witnesses fail my gremlin-trap:

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

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.