Martin Rubey wrote:
> I played a little more with PRIMES, more precisely with
> rabinProvesComposite and prime?
>
> There are at least two things unclear. For example, we have (globally)
>
> rootsMinus1:Set I := empty()
> -- used to check whether we detect too many roots of -1
> count2Order:Vector NonNegativeInteger := new(1,0)
> -- used to check whether we observe an element of maximal two-order
>
> rootsMinus1 is the set {b^(q 2^(j-1)) : b^(q 2^j) = -1 mod n}
>
> Clearly, when rootsMinus1 contains more than two elements, then n cannot
> be a prime. However, I could not find *any* number such that this
> condition would be triggered in rabinProvesComposite.
>
AFAIK such cases are extremally rare, it is almost impossible to find
such case via random search and systemtic methods to find them
are quite heavy.
> count2Order(j) = #{b: b^(q 2^(j-1)) = -1 mod n}
>
> When count2Order(k)>0 (remember q 2^k = n-1) then n must be prime, since
> then b has order n-1. However, count2Order(j) for smaller j seems to be
> unused, and I can't think of a good use for them. Moreover, the first
> test count2Order(k)>0 appears very late. Testing earlier seems to be
> *very* effective.
>
> Can I commit? (after a little more testing
Please wait a bit: I looked at rabinProvesCompositeSmall in the past
and it looked correct and well optimized. It is quite easy to
make it worse -- I would like to have some time to look more
carefully at your version.
--
Waldek Hebisch
[email protected]
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/fricas-devel?hl=en.
