Re: JSH: What are you people?

On 23 Jan, 04:11, Rotwang <sg...@xxxxxxxxxxxxx> wrote:

[...]
You get lots of a's, but most of them do not correspond to
factorisations of T. For example, with T chosen to be a product of two
(not necessarily distinct) primes from the set
{431,677,967,1187,1429,1621} and p chosen from the set
{433,683,971,1193,1422,1627}, my program found 132812 (a,k) pairs
which satisfied k^2 = (a^2 + 1)^(-1)T mod p, but only 424 of these
were equal mod p to a factor of T.

One curiosity I found is that if the factors of T and the values of p
are chosen from the same set, the method systematically found many
more non-trivial factorisations than trivial ones, though not if they
were chosen from different sets (as with my example above). Does
anybody know why?

Having thought about it for a few minutes, it's fairly obvious: if p
is a factor of T then there is a non-trivial factorisation T = f1*f2
with f1 mod p = 0, and k = 0 satisfies k^2 = (a^2 + 1)^(-1)T = 0 mod p
for any value of a, which gives p - 1 (a,k) pairs that work.
.