Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

presume: we have A and B integers, and C - product of multiplication of A and B, A and B are prime numbers (strong or usual) G - is geometric mean of A and B (square root of C) also, we have: if B > A => G/A = B/G (from geometric mean properties) so: since G is float number, then GCD(G*10^x,C) > 1 and I can with trial and error change x to conforming value (bruteforce)

However, it works on small numbers (32 bits) and can't work on RSA numbers. What is the problem? Multiplier's relation, computation error or something other?

Here is C pseudocode for this question: //c = a * b

g = sqrt(c); for(i=1000;i;i--) { t = int(g*(10^i)); if(gcd(t,c)>1)break; } print gcd(t,c);

I made test code with GMP lib, however it works only on 32 bit C (is it a computation error on GMP side or some relations between multipliers of C in RSA challenge numbers?) If method works on small numbers it must works on any numbers, right? Even if multipliers in RSA of similar numbers have some relations, it can be diluted by some third multiplies.

Power of 10 multiplication makes G integer (without changing it's nature) since G initialy float number. So, if exist number N which is integer and (G*10^x)/N=A(or B)*n, G*10^x will have common divisor with C.

share|improve this question
2  
What makes you think that arbitrarily truncating $\sqrt{c} \times 10^i$ for any $i$ will give a meaningful integer with the properties you describe? The reason it works for small numbers is that some $i$ ends up giving a factor by chance, obviously that doesn't happen for larger integers. I don't follow your geometric mean argument - how does it relate to multiplying the mean by a power of 10? Why not a power of 2? What's so special about 10? (I think this is where your argument breaks down - $g$ is irrational so you'll never get an integer, perhaps you were thinking of continued fractions?) –  Thomas Jun 30 '13 at 8:58
add comment

1 Answer

In response to your edit, this is where you made a mistake:

Power of 10 multiplication makes G integer (without changing it's nature) since G initialy float number. So, if exist number N which is integer and (G*10^x)/N=A(or B)*n, G*10^x will have common divisor with C.

Unless $c$ is a perfect square (i.e. $a = b$, this can be efficiently checked because $\sqrt{c}$ is then already an integer), then $g = \sqrt{c}$ is irrational, which means its fractional expansion is infinite and nonrepeating. Therefore there exists no integer $i$ such that $g \cdot 10^i$ (or in any other base, for that matter) is an integer.

The fact that computers can only store a certain amount of digits is completely besides the point, even though you may (and probably will) eventually force the computer into giving you back an integer, that integer doesn't mean anything since it doesn't represent a mathematical result but merely the inability of the computer to correctly represent arbitrarily many decimal digits.

In other words, the sequence $\{ \lfloor \sqrt{c} \cdot 10^i \rfloor \mod{c} \mid i \in \mathbb{N} \}$ is for all intents and purposes a pseudorandom sequence of integers, so this isn't any better than the brute force approach of taking the $\gcd$ of arbitrary, randomly picked integers with $c$ (which will "work" for small numbers as you observed, but is exceedingly unlikely to find a factor with large semiprimes the size of RSA moduli)


However there are factorization methods loosely based on what you suggest which are capable of factorizing integers with decent performance (continued fraction algorithms take around $O(\sqrt[4]{c})$ time).

Look up the CFRAC algorithm, for instance. It calculates the continued fraction expansion of $\sqrt{kc}$ (using your notation) for a few integers $k$, and uses the resulting expansion to obtain a recurrence encoding the factors $a$ and $b$ of $c$. As you can see, there is potential in using the square root of the integer to factor, but I'm afraid the way you suggest doesn't lead to anything very useful.

SQUFOF is also worth taking a look at, it is similar to CFRAC but may be easier for you to follow.

Note none of these algorithms are fast enough for very large numbers, sadly. But they are useful in that they sometimes form the (theoretical) basis of the more powerful algorithms, and are simple enough for people to implement and experiment with, unlike modern factorization techniques which require nontrivial math knowledge with many subtle implementation details.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.