[quote=Greenbank;226794]It raises an interesting theoretical question though, is there any way that I can prove that I've factored the number without revealing enough information to give away the factors? I'm guessing not.[/quote]An approach I've used in the past is to use the 20 most significant digits of one of the factors as the passphrase for a conventionally encrypted PGP message, the plaintext of which gives the complete factorization.

As far as anyone knows, factoring a moderately large integer is computationally less demanding than exhaustive search over a 10^20 keyspace.


Paul

[QUOTE=xilman;226805]An approach I've used in the past is to use the 20 most significant digits of one of the factors as the passphrase for a conventionally encrypted PGP message, the plaintext of which gives the complete factorization.

As far as anyone knows, factoring a moderately large integer is computationally less demanding than exhaustive search over a 10^20 keyspace.


Paul[/QUOTE]


Zero knowledge proofs exist for knowing the factorization of a number.

[quote=R.D. Silverman;226811]Zero knowledge proofs exist for knowing the factorization of a number.[/quote]I know. However, the sort of people who ask for factorizations of relatively small numbers without providing justifications are invariably the sort of people who have no idea what a ZKP means nor how to verify my provided evidence. They do understand secret-key cryptography to the depth necessary to understand my offer to provide the secret key protecting the complete factorization in return for the reasons why they want the factors.

Paul

[QUOTE=warut;226804]See [URL="http://www.loria.fr/~zimmerma/records/rsa.html"]here[/URL] for a simple scheme to show that you know the factorization. Then show me your [I]c[/I].[/QUOTE]

Excellent, will do that when I'm back at the machine that has the factors (I got part way through a GMP program to calculate the numbers before realising I didn't have the factors to hand!)

Whenever someone posts a number they need factored, I always try a google search on a run of a few (~10) digits for the number. I've never gotten any hits that would give a clue where it came from. You'd think that out of all the times I've tried I would have caught somebody being careless. Especially with 512-bit numbers you'd think there's a reverse engineering forum somewhere that would have the number printed. Plenty of those forums let google index them even if they require a login when you visit directly.

Isn't posting the square root mod N of a small prime sufficient to prove that you have the factorisation?

[QUOTE=Greenbank;227083]Excellent, will do that when I'm back at the machine that has the factors (I got part way through a GMP program to calculate the numbers before realising I didn't have the factors to hand!)[/QUOTE]

N = 67265468438158925156029310985265926133792339483088426060945720579389614045244727695101069671293650665794246539609007915477818493

c = 31076913792279226852779303483036033604443201834656522894105173299376532491413417055125619403032537426735638843325467459739385573

c^65537 mod N = 3

[QUOTE=fivemack;227132]Isn't posting the square root mod N of a small prime sufficient to prove that you have the factorisation?[/QUOTE]

With high probability........:smile:

[QUOTE=fivemack;227132]Isn't posting the square root mod N of a small prime sufficient to prove that you have the factorisation?[/QUOTE]
I could easily post two square roots of 2 modulo any Fermat number greater than 5. But with nontrivial factors given, I could post more... :big grin: