Re: JSH: What are you people?

On 23 Jan, 06:12, JSH <jst...@xxxxxxxxx> wrote:
On Jan 22, 9:45 pm, Rotwang <sg...@xxxxxxxxxxxxx> wrote:

OK, so now you are claiming that given a and k satisfying k^2 = (a^2 +
1)^(-1)T mod p, there is a 75% chance that there exists a factor f of
T satisfying f = ak mod p, is this the correct interpretation? If so,
then based on a program I just wrote which systematically found values
of a and k with f1,f2 and p taken from a list of primes, I believe
that this is false.

Your belief is irrelevant.

Then so is yours. But what aren't irrelevant are the results of my

You sound petulant.

And you sound asinine. But I was too polite to point it out.

My belief IS irrelevant though.

And your program has problems.



program, if I didn't make a mistake (and if I haven't once again
misinterpreted what your claim is supposed to be - could you go to the
trouble of confirming my above guess?). If you don't believe the
results I gave you can run the program yourself. Here is the Python
script:

def Src(Q,R):
yet = 0
yen = 0
tot = 0
for f in Q:
for g in Q:
if g >= f:
for p in R:
for a in range(1,p):
for k in range(0,p):

Why would you loop from 0?

Why not? I don't recall that you specified that k should be non-zero.
But no matter: changing the program to loop from k = 1 and running
again with the aforementioned inputs gives ... exactly the same
results.


What are you thinking here?



if ((a*a+1)*k*k)%p == (f*g)%p:
tot = tot + 1
if (a*k)%p == f%p or (a*k)%p == g%p:
yen = yen + 1
elif (a*k)%p == 1 or (a*k)%p == (f*g)%p:
yet = yet + 1
print yet, yen, tot

The function takes two arguments; the first is a list of primes from
which the factors of T are drawn, and the second a list of primes from
which p is drawn. tot counts the total number of (a,k) pairs found,
yen the number of those which give f1 equal mod p to a non-trivial
factor of T, and yet the number of those which give f1 equal mod p to
a trivial factor of T. I just ran it several times with Q =
[431,677,967,1187,1429,1621] and R = [683], [971] and [1433]. Each
time it actually gave *fewer* f1's which were equal mod p to a factor
of T than you would expect to get by simply picking f1 at random from
the set {1,2, ... p-1}. That's quite a bit less than 75%.

Fix the error I found and then I'll consider the rest.

I wouldn't be surprised if I found more.

Part of my problem here is that I'm dealing with loud people who do
not necessarily have any real skills.

I say that to warn others who may read too much into replies that I
get.

[...]
The CRT won't help you here: if you want it to guarantee you a single
value of f1 less than sqrt(T) (similar to what you get if you know f1
mod p for p > sqrt(T)) then you need to know f1 mod p_n for a set of
primes {p_n} whose product is greater than sqrt(T). However, having
found values of a and k for each p_n, there is no way of knowing
whether the values they give for f1 mod p_n are correct and correspond
to the same factor. Thus in the worst case scenario you are forced to
check whether the f1 given by the Chinese remainder theorem works for
every possible combination of a_n's with a_n a positive integer less
than p_n. And of course the number of such combinations is not much
less than sqrt(T), so it looks a lot like nothing has been gained.

Ok, hypothetically consider an RSA public key with two prime factors
f_1 and f_2, and you find f_1 mod p_j and f_2 mod p_j, and wish to
consider whether or not those are the trivial factorization or the non-
trivial one, unless f_1*f_2 mod p_j equal f_1 mod p_j and f_2 mod p_j
= 1 or -1 mod p_j, that is easy.

This still isn't good enough, even if your 75% estimate is correct.
You need to know f1 mod p_n for a lot of small primes if you want to
factor an RSA-sized number; even if you can rule out those that give

Your vagueness is infuriatingly non-mathematical.

For you of all people to make this complaint is quite ridiculous. I
notice that you *still* haven't confirmed my guess as to what your
"theorem" is supposed to mean.


The proper answer is that the total number j of primes it would take
is less than m such that T/m! < 1.

No, the proper answer is what I said before: the product of the primes
should be greater than sqrt(T). The number you give is actually an
overestimate.


trivial factorisations (which you need to do separately for each n
since you will need to find different (a,k) pairs for each n), you
have the problem that you don't know which of f1 mod p_n and f2 mod
p_n is which, nor which of the 25% of your f1 mod p's don't correspond
to a factorisation at all. Though this might still lead to an

Just multiply times 2, or 3 or some other small prime to pull out
valid factorization eliminating concerns about the 25%.

I'm afraid I don't follow this at all. Can you explain in more detail
how this is supposed to work?


That's why I left it z^2 = y^2 + nT, as you can adjust n at will, as
long as it is integer and non-zero.

As for the issue of which is which as you loop through p's now that is
a much better issue.

There may be an oddly simple answer which would be verified by
experiment, which is that the math may give you the same f_1 each
time.

"May"? I thought math was about absolutes? That was what you lectured
me with last time I used the word "may", wasn't it?


I don't know as maybe it doesn't but I think it does.

What you think is irrelevant. Either it does or it doesn't.

(If you find petulant replies annoying, you should probably cut down
on the kind of asinine posts that ask for them)

[...]
.

Relevant Pages

  • Re: JSH: What are you people?
    ... tot = tot + 1 ... which the factors of T are drawn, and the second a list of primes from ... a trivial solution to the factoring problem. ... It is EASY ALGEBRA, throughout. ...
    (sci.crypt)
  • Re: JSH: What are you people?
    ... tot = tot + 1 ... which the factors of T are drawn, and the second a list of primes from ... valid factorization eliminating concerns about the 25%. ... It is EASY ALGEBRA, throughout. ...
    (sci.crypt)
  • Re: JSH: What are you people?
    ... while with three primes there are six. ... tot = tot + 1 ... valid factorization eliminating concerns about the 25%. ... It's EASY algebra to look through. ...
    (sci.crypt)
  • Re: JSH: What are you people?
    ... tot = tot + 1 ... you get a 75% probability. ... the last few weeks (even though it's EASY ALGEBRA ) suggests that ... Then type Srcwhere Q and R are lists of primes ...
    (sci.crypt)
  • Re: JSH: What are you people?
    ... while with three primes there are six. ... which will be one of the integer factorizations. ... tot = tot + 1 ... consider whether or not those are the trivial factorization or the non- ...
    (sci.crypt)