tea.mathoverflow.net - Discussion Feed (Number of divisors of an integer of form 4k+1 and 4k+3)

Pete L. Clark comments on "Number of divisors of an integer of form 4k+1 and 4k+3" (13709)

2011-03-19T12:37:26-07:00

@Mark: "Isn't it true that factoring a number of the form $pq$, $p,q$ are prime, is as hard as factoring any number and the RSA codes are based on this?"

It is believed to be true, at least, and the RSA scheme is based on this belief. So far so good...

markvs comments on "Number of divisors of an integer of form 4k+1 and 4k+3" (13683)

2011-03-18T20:06:54-07:00

Isn't it true that factoring a number of the form $pq$, $p,q$ are prime, is as hard as factoring any number and the RSA codes are based on this? If so, then the oracle giving the number of prime divisors of the form 4k+1, 4k+3 won't help much.

Douglas Zare comments on "Number of divisors of an integer of form 4k+1 and 4k+3" (13680)

2011-03-18T13:06:06-07:00

Thanks.

Yemon Choi comments on "Number of divisors of an integer of form 4k+1 and 4k+3" (13679)

2011-03-18T12:37:45-07:00

I have just cast the fifth vote to re-open the question, based on comments here and on the original post.

Douglas Zare comments on "Number of divisors of an integer of form 4k+1 and 4k+3" (13678)

2011-03-18T12:29:21-07:00

Why didn't I put that in the edit of the question? It's not equivalent to the original question, it's just one possible approach for showing that the answer is "no." If the approach pans out, then perhaps it would fit as an answer.

Please reopen the question.

unknowncom comments on "Number of divisors of an integer of form 4k+1 and 4k+3" (13677)

2011-03-18T11:17:28-07:00

I am the unknown that left the first comment on the question. I am also surprised it got closed, in particular as 'too localized' and none of the people voting to close giving any reason.

It is certainly true that the question at first was not quite clear and not well-written.
Thus, also resulting in different interpretations by Gerhard Paseman and me.
However, the comment of the questioner on GP's answer clarifies the issue.
In particular, even before Douglas Zare's edit (which now makes it completely clear) and thus before the closure, I'd say that reading
the full question (including what already happened in answer and comments) it was clear what was the intention.

Of course, one could say that the question should have then been edited accordingly (or better written in the first place),
but then at least this could have been pointed out to the questioner explictly (a relatively new user).

So, as the clarity issue is resolved, the substance issue:

As I see it, this question is 'philosophically' very likely essentially the same as the two questions now linked in the comments
(one by Peter Shor and the other by me), which were both very well-received questions.

The reason why I believe this, is that in all these questions, in one case very explcitly and in the two other cases (including the present one) somewhat implictly, the question boils down to saying 'something' on the (prime) divisors.
And, typically it is believed that in this context being able to say 'something' is more or less as difficult as being able to say 'everything' thus factoring. [This is much better explained in answers to the question I linked to in my comment on main, and also Joe Silverman on the question.]

However, while I consider it as likely to be so, I was/am not sure that this is so, for this precise problem (and so far nobody said so or otherwise). For some reason there could be a short-cut, or a definite argument that there is none.
Thus, also my action of pointing out the similarity and the answers on the other question.

What I did (on purpose) not do, is reiterating in an answer something already said recently for two questions (though not by me) on the site. [Also I have no intenetion to give an answer as I have no additional insight to offer.]

My opinion is thus, if anything, it could be closed as 'duplicate'.

Yet, it is not an exact duplicate, and it is not excluded that sooner or later somebody comes along and has more specific insight to offers, which s/he can (meaningfully) only do if the question is open.

Also, I cannot see the point of closing the question (and I remember similar instances where I had similar feelings);
if one finds it a distraction, for whatever reason, I'd say it is best to leave it alone. After all, if it would not have been closed
it would not have been bumped just now. (Well, in the end it was maybe good for the question to be closed, if it is now reopened.)

Deleted ADDED (Sorry for the repeated edits!)

Other ADDED: Personnaly, I would not prefer the 'oracle' formulation; as it is in one form implict in the present question,
and asking it alone would yield a more narrow question.

markvs comments on "Number of divisors of an integer of form 4k+1 and 4k+3" (13676)

2011-03-18T10:16:42-07:00

"It would be interesting if someone could prove that if you had an oracle which told you the counts of divisors of the form 4k+1 and 4k+3, then you could factor n rapidly."

Yes, I agree, it is interesting (much more than the original question). Why don't you include it in the question or perhaps ask a separate question.

Douglas Zare comments on "Number of divisors of an integer of form 4k+1 and 4k+3" (13675)

2011-03-18T09:42:50-07:00

http://mathoverflow.net/questions/58702/number-of-divisors-of-an-integer-of-form-4n1-and-4n3/58709
This question was closed as too localized. I think this was due to people misreading the question, which seems far from trivial. I have rewritten it, but from my perspective the essence of the question is the same.

It would be interesting if someone could prove that if you had an oracle which told you the counts of divisors of the form 4k+1 and 4k+3, then you could factor n rapidly.

I have a formulation of the Riemann hypothesis that I think would be closed as "too localized" if I were to post it anonymously.