Re: JSH: What are you people?

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

On Jan 22, 8:11 pm, Rotwang <sg...@xxxxxxxxxxxxx> wrote:

I don't believe that this is what Enrico found (though I'm not
entirely sure what he did find - looking again at his post in the
"Counting a's" thread it's not at all clear to me what he was
searching for in terms of properties of the a's).

Well that sounds honest.

Other posters were definitely less so.

I doubt that. The fact is that it's frequently very difficult to
figure out what your ambiguous statements are supposed to mean, and
it's not dishonest if people misinterpret data based on having to
guess what you think is true.


The issue was figuring out what Enrico was meaning.

Other posters declared with certainty while you did not.



So, with two primes there are two unique factorizations, the trivial
one and the non-trivial one, while with three primes there are six.

Of that total, 75% of them will give an integer solution for z and y,
which will be one of the integer factorizations.

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.

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?

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.

Which is trivial to do for a small prime, so you can have p_1, p_2,
p_3,...p_n, where n is a natural number where an easy way to estimate
the size of n, is to note that it is less than m such that T/m!<1.

And then you just use the Chinese Remainder theorem to get a factor.

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.

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

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%.

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.

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

It's EASY algebra to look through. The two equations for f_1 and f_2
are asymmetrical, as in one looks different from the other.

It's quite possible that they are picky in highly specific ways.

I will admit I haven't checked as I'm just speculating while making a
quick reply.

algorithm which has a high probability of factoring large numbers
quickly if your 75% estimate were true, but it isn't.

Hey, the 75% number comes from mathematical proof.

The relations are derived.

It's easy algebra.

There are only a few areas to attack here, as so much is derived from
VERY simple algebra.

Now maybe you wish to attack the foundations of mathematics, but I for
one feel confident that algebra is fairly well-founded, so I suggest
you concentrate instead on areas where you may actually find something
of interest.


James Harris
.

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 ... valid factorization eliminating concerns about the 25%. ... 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 ... a trivial solution to the factoring problem. ... It is EASY ALGEBRA, throughout. ...
    (sci.crypt)
  • Re: JSH: What are you people?
    ... T satisfying f = ak mod p, is this the correct interpretation? ... 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%. ...
    (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)