That's quite some paper! The 10147 sample with a brute force approach (divide by each prime from a known prime list and see if the result is a prime as well) is shorter than your sample:
``````
10147 /   2 =  5073 rest 1
10147 /   3 =  3382 rest 1
10147 /   5 =  2029 rest 2
10147 /   7 =  1449 rest 4
10147 /  11 =   922 rest 5
10147 /  13 =   780 rest 7
10147 /  17 =   596 rest 15
10147 /  19 =   534 rest 1
10147 /  23 =   441 rest 4
10147 /  29 =   349 rest 26
10147 /  31 =   327 rest 10
10147 /  37 =   274 rest 9
10147 /  41 =   247 rest 20
10147 /  43 =   235 rest 42
10147 /  47 =   215 rest 42
10147 /  53 =   191 rest 24
10147 /  59 =   171 rest 58
10147 /  61 =   166 rest 21
10147 /  67 =   151 rest 30
10147 /  71 =   142 rest 65
10147 /  73 =   139 rest 0
10147 is evenly divisible by 73, and the result is a prime!
Solution found: 73 x 139
``````

Of course you wouldn't do brute force on paper but I'm trying to get an idea of the amount of work needed for a brute force approach compared to your method.
I tried it with 1442500261 and the program came up with 17491x82471 after a few seconds using 2013 divisions like above so the number of operations increases at high rate.
500 sheets of paper do seem a lot of work but not impossible, it would be nice if you could let your PC do it for you :).

Thomas
Posted on 2002-05-12 16:00:32 by Thomas
I'm still not sure if there's a secret process or formula.
Here's something using cryptarithmic notation.
``````
**abcd          ***abc
***efg          **defg
------          ------
**ABCD          ***ABC
**EFGH          ***DEF
**IJKL          ***GHI
*******          ***JKL
*******         *******
*******         *******
------------    ------------
*********XYZ    *********XYZ
``````
If a-g represent known digits, then only the digits A-L and X-Z are also known. Thus for each known least significant digit in the product, you must know at least as many digits in both factors. In other words, the last three digits of the product are completely determined by the last three digits of both factors.

Let's assume you have a partial solution set Sn of ordered pairs <pn, qn> that determine the last n product digits. For the new partial solution set S(n+1) in base r, you need to test (r^2 * |Sn|) possibilities for inclusion. You can't omit 0 (101 is prime), and you can't assume the last digits must be prime (127 is prime).

I see optimizing opportunities for this basic strategy.
Posted on 2002-05-12 16:05:04 by tenkey
Thomas, no need for brute force: the most modern software algorithms, on a normal PC, can break in reasonable time a 460bit key, IIRC.

500 sheets of paper for a 576bit key would be great, though, if it was true (not stating it is not, I'm just saying I still have no evidence of it).
Posted on 2002-05-12 16:59:29 by Maverick
``````
...112345678         112345678*100000000
....112345678        112345678*10000000
.....112345678       112345678*1000000
......112345678      112345678*100000
.......112345678     112345678*10000
........112345678    112345678*1000
.........112345678   112345678*100
..........112345678  112345678*10
..........?112345678 112345678*1
--------------------
..........7098628258 m
----------4333322100 carry
``````

As you will have noticed, finding the missing 1 didn't mess up your results, but the next step could. If it doesn't, you could be pretty sure your pq pair is right, and you may forget about 8 decimals (1*10E7 possibilities). The hidden task number must be a multiple of 112345678, and summing them to the known numbers plus the carry, you are able to find the missing number. Doing it the other way round, you assume the missing number to be 0...9 and see if any multiple of 8 would sum to give 7. This is exactly what the algo does.

``````
...112345678         112345678*100000000
....112345678        112345678* 10000000
.....112345678       112345678*  1000000
......112345678      112345678*   100000
.......112345678     112345678*    10000
........112345678    112345678*     1000
.........112345678   112345678*      100
..........112345678  112345678*       10
..........0112345678 112345678*        1
----------------------------------------
..........7098628258 m         111111111
----------4333322100 carry
...12482853098628258 (calc.exe)
^

4+0+1+1+2+3+4+5+6+7=33+4=7

112345678*1=112345678
112345678*2=224691356
112345678*3=337037034	*
112345678*4=449382712
112345678*5=561728390
112345678*6=674074068
112345678*7=786419746
112345678*8=898765424	*
112345678*9=1011111102
112345678*10=1123456780

??????????           (unknown)
.0337037034          0112345678*3000000000
..0112345678         0112345678* 100000000
...0112345678        0112345678*  10000000
....0112345678       0112345678*   1000000
.....0112345678      0112345678*    100000
......0112345678     0112345678*     10000
.......0112345678    0112345678*      1000
........0112345678   0112345678*       100
.........0112345678  0112345678*        10
.........?0112345678 0112345678*         1
-----------------------------------------
.........n7098628258 m         3111111111
---------34333322100 carry
..349519887098628258 (calc.exe)
^

``````

Substituting the upper questionmark by a multiple ending of 8 and the lower by an increasing count, you could get a loose match, or you find out, nothing is matching.
Well, if it is, your 'q' becomes almost definitively [3]111111111, and your 'p' could be assumed to be 112345678. At this point you'll need a sort of sliding bookmark which could upgrade much easier than before.
Note: without carries it's almost impossible to verify a match, and all the calc's are nothing more than a brute force attack.

That's all, folks. No more secrets. End of Level 1. Level 2 is made by some observations, but I have to work them out before. Part of this level is for my own to have a nearer look at binaries, which I had not yet, and some adds to the BNLib. I want to have a close look to bitRakes patterns and to the amplifying effects of good and wrong initial choices in relation to the final stages. My friends have worked out a PC algo, and I have to follow them too, a little (stack problems).

I anticipated this, because this way I free my (limited human) resources for the following tasks, which are unavoidable. Main reason for this step was my sunday's task, which showed me clearly where my mental limits are.

Sunday's I had a nearer look at RSA-2048. My good pq endings are 107*51 (verified twice) and some doubts about 10107 and/or 751. Doing this in very short time was not so difficult, but all night and today I tried to stop to think about it, without any success. Please don't go into a loop like me. It doesn't help at all :) I never believed it's possible to go in love for numbers!

RSA-2048 is extremely difficult, because it doesn't produce enough carries at the beginning, and has to be verified deeply, and not loose.

bitRake: There could be even more possibilities than 40 on 2 digits. Once you pass to 3 digits, these possibilities are reduced to very few. The uneven couple of pq do the verifying step of the even switch. If you have 1*9 couples, you may not verify them before doing an 11*9 or 1*19. If your choice has been 11*9, 11*19 does nothing else than to prepare a new assumption, and n11*19 will verify that. Note that having, for example, 03 and/or 07 to verify, 103 * 07 gives a different result from 03 * 107 and different carries, too. If the numbers are good enough you'll find out 1 or 2 digits later. Anyway I noticed some behaviors on binaries which is interesting, especially on base 16. I believe, but don't know (this is why I have to try it first), having a greater numerical distance between digits, I could preview better. On the other hand, for some tasks a finer step could help to find difficult endings, but this, too, I don't know. If the chosen base helps to solve common problems, such as predicting a more probable ending, I will have to have some studies on the granularity too.

I like this forum. It opens the mind. Thank you all for keeping it alive.

Giovanni

PS: If I could, I would prove my algo wrong, because I never imagined to get my mind involved this way. I feel completely exhausted, and still I cannot stop doing estimates all the time. Instead of drawing figures while phoning, I have always the 720357 ending printed in my mind, written on every peace of paper, and try to guess the right missing numbers for 72[0]. I think I need a break :) !

How you are going?
Posted on 2002-05-13 13:29:14 by sch.jnn
I'll tell ya,

Giovanni, this is a tough one......
As BitRake, similarily said earlier, I also have spent many hrs trying to Tri-sect an angle, even though it is proven un-tri-sectable.....I know that it is only proven in a given space/projection...... this is a similar problem.......maybe not reasonably solve-able....I say this to.... maybe relieve the obsession that I have experienced many times....

I Really thought (and Still do) that you are on to a solution....how-ever "I" believe that we must step back a little....and try to reduce the directives....."we must reduce the equation/number as we realize a digit....otherwise....it gets too ridiculous.....(one possibility....even though I haven't been able to work it....is: to use a "target reference" such as "11" to find whether were high or low.....)....I don't know....been way to busy with a new contract......but this is a good one....:)

Posted on 2002-05-13 22:30:46 by Brad
After starting a more thorough list of possibilities, it became obvious that bitRake is right...there are 40 pairs of 2-digit "tails" that yield the same last two digits (if the last digit in the product was 1, 3, 7, or 9). There are 400 pairs of 3-digit tails that yield the same last three digits. The number of possibilities increases 10-fold for each digit until the length of the factor tails equals the length of the square root.
Posted on 2002-05-14 03:16:05 by tenkey

As BitRake, similarily said earlier, I also have spent many hrs trying to Tri-sect an angle, even though it is proven un-tri-sectable.....I know that it is only proven in a given space/projection...... this is a similar problem.......maybe not reasonably solve-able....I say this to.... maybe relieve the obsession that I have experienced many times....

I Really thought (and Still do) that you are on to a solution....how-ever "I" believe that we must step back a little....and try to reduce the directives....."we must reduce the equation/number as we realize a digit....otherwise....it gets too ridiculous.....(one possibility....even though I haven't been able to work it....is: to use a "target reference" such as "11" to find whether were high or low.....)....I don't know....been way to busy with a new contract......but this is a good one....:)

Giovanni
Posted on 2002-05-14 03:19:48 by sch.jnn

I see optimizing opportunities for this basic strategy.

Me too. The only problem is I am doing by hand something what I am not able to explain yet, because I don't see *what* I am doing exactly. But I do some optimizing steps.

Giovanni
Posted on 2002-05-14 09:17:33 by sch.jnn
hi,

just want to say, you should publish a *clear*, mathematically written algorithm, so everybody knows what we' re talking about, not just endless list of numbers with fuzzy patters, how d' you wanna make serious time estimates with fuzzy patterns ? from what i' ve see, it appears that your algorithm is just an 'optimized basic bruteforce search', i guess it' s complexity is even worse than pollard' s rho. you should start doing something mathematically *correct* =)
Posted on 2002-05-14 12:55:42 by roy
Roy, ????????

You need to go back and re-read the thread..... The whole purpose of this thread is to try to get who-ever interested,
to help write the algo.....which has yet to be completely understood....by any-one....

Posted on 2002-05-14 19:09:36 by Brad
If he goes back and re-reads the thread, what he finds is:

original post written by sch.jnn:
I've found an easy end extremely fast way to cr*ck any public exponent, if it is the result of two primes. That means in other words, RSA is actually cr*cked.
That to me clearly reads like "I have the algorithm".
Instead if one doesn't even have the algorithm, then he has got nothing, besides some will to moan and say he was unjustly mistreated by other people simply pointing what I've just re-pointed out above, kindly.
Posted on 2002-05-14 19:45:12 by Maverick
Maverick,

again ????????

Giovanni never said he had an algorithm....he said he had a procedure which could lead to an algorithm.....

Further....once you learn to give respect...you will learn to recieve the same....and then you will learn to demand it.....I never heard any "moaning"...just disgust :mad:

Posted on 2002-05-14 20:09:43 by Brad
Algorithm and procedure are the same thing. He said he cracked the RSA and that it's damn easy and extremely fast. Both are false, until proven otherwise. That's the whole point.

I never lacked him respect.

The disgust is mutual, thanks. :)
Posted on 2002-05-14 20:37:06 by Maverick
Ok,

Giovanni has showed you a procedure.....how do you code the algo? :)
Posted on 2002-05-14 20:41:17 by Brad
Again, in this context procedure and algorithm are sinonims.

I've nothing against Giovanni, but he got offended for just my pointing out that there was very little substance underneath until then (and also until now), unlike others which made jokes on him (something I find unacceptable); and also I think it's immature when e.g. he talks about stack problems, I tell him how to solve them, and he keeps on posting like if his problems keep on being there.. like a kid that simulates the non-existance of somebody. Blah. I thought we were older than that, and just looked at the technical substance of things.. but evidently that's not what he does.

It's childish, like his lack of algorithm, which makes his initial claims false, big, huge, unproven, a serious waste of time.
original post written by sch.jnn:
I've found an easy end extremely fast way to cr*ck any public exponent, if it is the result of two primes. That means in other words, RSA is actually cr*cked.
Now if he is offended by this, it's his problem.. I've been honest in my thoughts, I'm a serious person and if I see some "alchemy" in a discussion instead of pure science I have to point that out. And will always do that.

Sure I wish he really cr*cked the RSA, but so far he did nothing at all. There are much, much better methods than brute force, one of them IIRC can find the factors of a 460bit RSA key on a normal PC in reasonable time. 460bits! Even if Giovanni's method worked, from what I've read above it would be much slower than that method I just mentioned (we can find its name and description if it's important).

So let's get serious, finally, please.
Posted on 2002-05-15 05:18:53 by Maverick
Now Now kiddies, playground fight outside please and no black eyes. :grin:

From what I have seen of this thread so far, RSA has very little to worry about.

==============================
I've found an easy end extremely fast way to cr*ck any public exponent, if it is the result of two primes. That means in other words, RSA is actually cr*cked.
==============================

The law of excluded middle (Russell and Whitehead [ Principia Mathematica 1914 ]) translates to the idiom as EITHER it "is" or it "ain't" but it cannot be both.

Since the technique has not been shown to work, it AIN'T so the original posting is a lot of noise with no content. Lets hope that it can be developed into a useful proof OR a proven failure as those who use RSA may be interested.

I am a "one shot pad" man myself so I wonder about all the noise anyway. :tongue:

Regards,

hutch@movsd.com
Posted on 2002-05-15 06:16:53 by hutch--
From what I have seen of this thread so far, RSA has very little to worry about

LOL.
Posted on 2002-05-15 06:22:19 by The Svin
I understand the algorithm and found that the products around the product which has the most digits right are the ones that are best to continue on. For example, the algo done on 4369:
(I ignore the possibility that one of the primes is 5 or 2)

The arrow(s) indicates the correct choice(s).
The star(s) indicates the product(s) with the most correct digits.

4369 = 257 * 17

1 1 1 -
1 3 3 -
1 7 7 -
1 9 9 *

3 1 1 -
3 3 9 *
3 7 21 -
3 9 27 -

7 7 49 * <-
7 9 63 -
9 9 81 -

--- Continue with numbers 7 and 7

7 7 49
7 17 119 <-
7 27 189
7 37 259
7 47 329
7 57 399 <-
7 67 469 *
7 77 539
7 87 609
7 97 679

--- Continue with numbers 7 and 57

7 57 399
17 57 969 * <-
27 57 1539
37 57 2109
47 57 2679
57 57 3249
67 57 3819
77 57 4389
87 57 4959
97 57 5529

--- Continue with numbers 17 and 57

17 57 969
17 157 2669
17 257 4369 * <-
17 357 6069 //
17 457 7769 //
17 557 9469 //
17 657 11169 //
17 757 12869 //
17 857 14569 //
17 957 16269 //

As you can see, the correct product seems to be almost always the one with the most correct digits or the one above or below that one. I don't know if this always is the case.
Posted on 2002-05-17 00:58:22 by gliptic
No polemic intended, but from what I see above even the slowest of the "brute force" algorithms would be much faster.

Can you estimate the amount of processing power for a number of e.g. 200 digits?
Posted on 2002-05-17 03:49:28 by Maverick
--- Continue with numbers 7 and 7

7 7 49
7 17 119 <-
7 27 189
7 37 259
7 47 329
7 57 399 <-
7 67 469 *
7 77 539
7 87 609
7 97 679

As you can see, the correct product seems to be almost always the one with the most correct digits or the one above or below that one. I don't know if this always is the case.
Not always the case. If the product of two primes ends in 69, and if one prime ends in 37, the other prime will also end with 37.
Posted on 2002-05-17 05:07:17 by tenkey