I have also noticed a pattern.
Check out http://www.math.utah.edu/~alfeld/Eratosthenes.html

73*139 = 10147
I run into these primes by accident, but I think I also have found a pattern.
I am currently working on two different ways to kinda predict the prime numbers used to produce a product.
One method works off of Sch.jnn's method of common endings, which I have found a diffinite pattern.

The other is merely an idea.
Posted on 2002-05-10 09:55:30 by syn
A little Off Topic:

Speaking of Sieves, I have a Circle Sieve, which plots pixels super extremely fast....if anyones interested:

http://www.powerbasic.com/support/forums/Forum6/HTML/002051.html

Posted on 2002-05-10 10:08:31 by Brad
I'm not sure if he actually did add the short explaining part of mail:

I can help you only very shortly. We start from the ending numbers we suppose they will be the right ones, make a choice on which column to start and we count from 0 up to 10 (if done in decimal), in binary it would be from 0 to 2 (10bin). We multiply both columns down until a reasonable ending has been found and mark this as a possible choice, meanwhile all impossible combinations are out (compared to the final result which is actually m).

We extract all possible choices and *change column*, or else you would just reproduce a very slow prime sieve which goes through all possible numbers, and not just about a plausible selection.

In the new column you repeat this count, and multiply, marking all good results. All which are above 'm' aren't, nor the ones where the partial product could never be reproduced by any combination of the actual "seed". You may not use the latter filter, and stages become heavily overloaded, but it would work, too.

I used the "false" condition (starting 1*7 on 10147) because it shows entirely how a tree is built.

Anyway, if you have some results from the second extraction, you repeat changing again column, and so forth. The "false" condition gives only plausible overflows, meanwhile the "true" condition tends to become stable very early.

It's important that only one digit is found at every positive result, and the rest is simply to be ignored, because it makes part of a number not found yet (even if it accidentally matches).

Once you've got a new ending digit, be sure you never change it again, since it would not change even with manual multiply. If you find out later, you'd need to change it, it's very probable you missed the right ending couple. If you didn't, somewhere you missed out a step. It could be a very long task to find out where it is. This is why I insisted not to hurry. Be sure too, to change the columns, because this would *virtually* happen if you would add assumed endings.

I've looked at bitRakes binary sample, but it was very late at night, and I was almost asleep (3:30). Anyway the binary number system allowes to do much finer tuning, but in the same time it becomes more confusing too, because the steps aren't 10 but 2 for each "digit". I've seen some 11 and 17's too, but this wasn't I've been looking for. But shifted numbers could actually be a better solution for guessing. I have to work this out first, and see if it could be an advantage.

Edit: It's an interesting pattern though.

Giovanni

PS: I've no time this evening and at work tomorrow. I've had a look to some of the indicated links, interesting. Sorry I've no time now.
Posted on 2002-05-10 11:04:24 by sch.jnn
After a simple investigation it would seem that
all primes other than 2 and 5 will end in
{1,3,7,or 9}

Using this apparent rule we can multiply any 2 primes together which end in {1,3,7,9} and notice that the result will always also end in {1,3,7,9}.

We can build this simple table:

1x3=3 3x7=21 7x9=63
1x7=7 3x9=27
1x9=9

=============================
Notice the ending digits: Extracted below:

1x3=3 3x7=1 7x9=3
1x7=7 3x9=7
1x9=9
=============================
To demonstriaght with higher numbers:

41*43=1763 43*87=3741
61*97=5917 73*89=6497
131*149=19519

107*119=12733
==============================
Notice once again the last digits always end the same.

Given this pattern we can guess the last digits of the secret prime numbers.

we can guess that the prime numbers end in either:

1 and 3
or
7 and 9

p has a last digit of '1' or '7'
and q has a last digit of '3' or '9'

I am trying to build on this concept to predict the 2nd and 3rd digits. I am finding futher patterns in the 2nd and 3rd digits, however I am still having trouble finding the overall pattern.

As below, I am able to find several interesting patterns:

When looking for Brad's primes for "36853"
I build the table below based on 7*9:

7*9=63
17*9=153 ** ends in 53
27*9=243
37*9=333
47*9=423
57*9=513
67*9=603
77*9=693
87*9=783
97*9=873
107*9=963
117*9=1053 ** ends in 53
127*9=1143
137*9=1233
147*9=1323
157*9=1413
167*9=1503
177*9=1593
187*9=1683
197*9=1773
207*9=1863
217*9=1953 ** ends in 53
227*9=2043
237*9=2133
247*9=2223
257*9=2313
267*9=2403
277*9=2493
287*9=2583
297*9=2673
307*9=2763
317*9=2853 ** ends in 53, and 853

7*79=553
7*179=1253
7*279=1953
7*379=2653
7*479=3353
7*579=4053
7*679=4753
7*779=5453
7*879=6153
7*979=6853 ** ends in 853
7*1079=7553
7*1179=8253

7*1279=8953
7*1379=9653
7*1479=10353
7*1579=11053
7*1679=11753
7*1779=12453
7*1879=13153
7*1979=13853 ** ends in 853
7*2079=14553

Let me know what you think.
Posted on 2002-05-10 11:30:01 by syn
I switched to binary because all you see is the pattern. ;)
``````Y = ...abcd1

X * Y =

...abcd1   the presense of all
...abcd1    lines are dependant
...abcd1     on bits in X being set
...abcd1
+ ...abcd1
--------------
.....tuvwxyz1 = Z

And the converse (Y * X) where X = ...a'b'c'd'1

if d'= 0 then d=z
if d = 0 then d'=z
if z = 0 then
d=d'=1
or d=d'=0``````
Posted on 2002-05-10 11:43:32 by bitRAKE
Svin: I'm really interested into that formula, but we must wait a bit for details, I'm busy here :)

Giovanni
Posted on 2002-05-10 15:47:35 by sch.jnn
137*269=36853

After many attempts to solve the problem based on patterns of the last digit, I failed.
I was unable to find any clear relationship between the first guessed 'ones' digit and the following 'tens' and 'hundreds' digits.
Give us a hint sch.jnn!

Then I used a different method, it took me about 30 attempts using this new method which is bascially just intelligent brute force. I basically just took the sqrt of 'pq', choose p and q as the nearest intergers to the sqrt, then incremented both p and q into opposite directions also making sure that the last digit of p and q corresponded as defined in my previous post.

191.97=sqrt(36853)
191*193=36863
189*197=
187*199=
183*201=
181*203=
179*207=
177*209=
173*211=
171*213=
169*217=
167*219=
163*221=
161*223=
.
.
.
.137*269=36853

Notice I decrease 'q' for each prime. When I reach a prime, I increment 'p' until it is a prime matching the new 'q' as defined with such a table as below:

1x1=1
1x3=3
1x7=7
1x9=9
3x3=9
3x7=1
3x9=7
7x7=9
7x9=3
9x9=1

Since 'pq' is 36853 ending with '3'
I am only concerned with primes making the matches:
1x3=3 and
7x9=3

Note that there are:
3 possibilities for '1'
2 possibilities for '3'
2 possibilities for '7'
3 possibilities for '9'

Therefore I guess any 'pq' with an ending digit of 9 or 1 is therefore harder to guess.

After solving for the primes for "36853"
I attemped to develop some cross digit equations. A way to guess the 'tens' digit based on the 'ones' digit previously guessed. I've found this to be difficult. I can only produce an equation with 2 unknowns and am trying to create a supplemental equation that would let me solve for some probable 'tens' digit numbers.

I think that alot of what were trying to do lies in such a link between the predictable 1st digit, and the following digits.

137*269=36853
--------------------

37*69=2553
37*169=6253
37*269=9953

137*69=9453
137*169=23153
137*269=36853

In this case,
the link between the digits are strong,
x37*x69=xx53

But somehow when I was trying to solve using sch.jnn's method, I could not predict theses values '37', '69'.
Have any of you found the digit link?
Posted on 2002-05-10 17:22:44 by syn
There is a serious problem here: actually you know which primes to test.. but when you will deal with giant numbers, you will not easily know what are primes and what aren't.. and to find this basic, simple information will take ages.

Dunno how much this limitation applyes to Giovanni's method, though.. since I haven't checked it (no time, sorry).

But I got an independent idea I may test in the following days, when I get some free time. If anything, it will be a nice experience, and may anyway open my mind in other directions.
Posted on 2002-05-10 17:36:46 by Maverick

In this case,
the link between the digits are strong,
x37*x69=xx53

But somehow when I was trying to solve using sch.jnn's method, I could not predict theses values '37', '69'.
Have any of you found the digit link?
Giovanni stated there is a third part. The link you talk about is give by the equations I put above and a basic property of numbers, but 37x69 = xx53 isn't the only solution:
``````	mov ebx,0
mov ecx,100

mov esi,ecx
mov edi,ecx
_0:
mov eax,edi
mul esi
div ecx
cmp edx,53
jne _1 ; found it
inc ebx
_1:
dec edi
jne _0
mov edi,ecx
dec esi
jne _0
; ebx are number of pairs that produce desired digits``````
Of the 10000 possible combinations 40 produce the two digits 53. Can you prove why 40? Hint: look at the equations I posted above and also think about this in base two - extrapolate to base ten and then the general solution. If the digits are the same (55 instead of 53) then there are 80 out of 10000.

RSA-576 is a 174 digit number, let us assume it is two 87 digit numbers. Of all the possible 87 digit numbers that could be multiplied together, looking at the first 87 digits of the product should be able to reduce that down to 8e86 out of 1e174. Doesn't look like much help so far. Need some analysis of the latter digits.
Posted on 2002-05-10 20:40:47 by bitRAKE

After a simple investigation it would seem that
all primes other than 2 and 5 will end in
{1,3,7,or 9}

Using this apparent rule we can multiply any 2 primes together which end in {1,3,7,9} and notice that the result will always also end in {1,3,7,9}.

We can build this simple table:

1x3=3 3x7=21 7x9=63
1x7=7 3x9=27
1x9=9

=============================
Notice the ending digits: Extracted below:

1x3=3 3x7=1 7x9=3
1x7=7 3x9=7
1x9=9
=============================

HEY! I said THAT first!!:grin: :grin:

However I am GLAD you actually took the trouble of extending this idea... :cool: It's so cool.... Must have been difficult, ne?

Although since we'll be needing a computer to solve this stuff without making our brains gibber and roll slightly to the left, I suggest we-all look for the stuff in the BINARY realms... I don't think we can expect the computer to actually work really fast with decimals...
Posted on 2002-05-11 03:10:42 by AmkG
Once you got into the algo by using a PC program, you'll have noticed that you have to take care about your stack space. You may have noticed too, that going into deeper stages, you may have simular results with different partial factors, which may or not give the desired result. And you will have found out, that the big work is to find a good second constant.

By having stated you're multiplying always the same number, you may easily reduce your needed stack space and allow to your program to make *loose* assumptions, that is, to assume very early that an ending factor combination to be true, even if it may not be so. Once you've got, let's say, about 8 numbers on each side (pq), you will be able to build a partial stage tree, which sums necessarily must return the searched ending of 'm'.

``````
p=...12345678
q=...111111111
...
....12345678         12345678*100000000
.....12345678        12345678*10000000
......12345678       12345678*1000000
.......12345678      12345678*100000
........12345678     12345678*10000
.........12345678    12345678*1000
..........12345678   12345678*100
...........12345678  12345678*10
...........?12345678 12345678*1
--------------------
..........7098628258 m
-----------333322100 carry
``````

The next searched number of 'p' signed by a question mark, could be determined easily by adding the carry of 3 and the sum of the already known numbers (3+1+2+3+4+5+6+7+8=39). Actually, the ending 9 + 1 gives 10, this giving us not only 0, but the next carry, too. Thus, we get 112345678, which has to be distributed on the partial stage tree. Does your new sum mess up the result? No? Please go on, your pq guess is right yet!

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

Do you see why I actually prefer to do it all by hand and gave up to program this?

---

Syn showed us with his table something which actually has not been explained yet, but is essential to this algo. In fact you have noticed, counting is done from 0 to 10, where 0 is the starting position of an assumed to be good condition. Syn went on with his counting, including 11, 12, ..., 31. If we had a lot of stack space, we could say, it was a possibility, at least to go up to 11.

``````
7*9=63
17*9=153 ** ends in 53
27*9=243
37*9=333
47*9=423
57*9=513
67*9=603
77*9=693
87*9=783
97*9=873
107*9=963
117*9=1053 ** ends in 53
127*9=1143
137*9=1233
147*9=1323
157*9=1413
167*9=1503
177*9=1593
187*9=1683
197*9=1773
207*9=1863
217*9=1953 ** ends in 53
227*9=2043
237*9=2133
247*9=2223
257*9=2313
267*9=2403
277*9=2493
287*9=2583
297*9=2673
307*9=2763
317*9=2853 ** ends in 53, and 853
``````

If you multiply two 1 digit numbers, the resulting carry may never be greater than one digit, and in the range from 0*0 (0) to 9*11 (99), the carry may never be greater than 9. This changes if you increase your range, and if you do, you must predict more digits on the column flip, with no advantage. Moreover, you may find a matching very early, but come into heavy troubles when switching column, because your assumed to be good endings may not be good any more, and you'll discover this very late. Once you found it's not working, it's almost impossible to do a partial rollback, because you don't know if your endings were composed by 1 or by 2, or even more digits, and you must do a complete rollback. If you found a stable combination instead, you don't know to which column to switch, and if you continue as if nothing happened, one of the factors could become very large, and the other stays more or less at it's size, which could be right, but usually isn't. In any case, if this has to happen, because m is made from pq very different in size, this will be obtained from rolling back.

On the other hand, doing more than 10 counts could accelerate the final stages, which tend to have less and less carries from the previous, but should be applied only if you are pretty sure your endings are bound to a valid prime. This requires a very restricted prime table which have the same endings, and having them available, you actually could do a brute force division to see if one of them is p or q.

The table below shows the relative endings and the eventual carry of each possible multiplication:

``````
n1	n2	res	end	carry
0	0	0	0	0
0	1	0	0	0
0	2	0	0	0
0	3	0	0	0
0	4	0	0	0
0	5	0	0	0
0	6	0	0	0
0	7	0	0	0
0	8	0	0	0
0	9	0	0	0
0	10	0	0	0

1	0	0	0	0
1	1	1	1	0
1	2	2	2	0
1	3	3	3	0
1	4	4	4	0
1	5	5	5	0
1	6	6	6	0
1	7	7	7	0
1	8	8	8	0
1	9	9	9	0
1	10	10	0	1

2	0	0	0	0
2	1	2	2	0
2	2	4	4	0
2	3	6	6	0
2	4	8	8	0
2	5	10	0	1
2	6	12	2	1
2	7	14	4	1
2	8	16	6	1
2	9	18	8	1
2	10	20	0	2

3	0	0	0	0
3	1	3	3	0
3	2	6	6	0
3	3	9	9	0
3	4	12	2	1
3	5	15	5	1
3	6	18	8	1
3	7	21	1	2
3	8	24	4	2
3	9	27	7	2
3	10	30	0	3

4	0	0	0	0
4	1	4	4	0
4	2	8	8	0
4	3	12	2	1
4	4	16	6	1
4	5	20	0	2
4	6	24	4	2
4	7	28	8	2
4	8	32	2	3
4	9	36	6	3
4	10	40	0	4

5	0	0	0	0
5	1	5	5	0
5	2	10	0	1
5	3	15	5	1
5	4	20	0	2
5	5	25	5	2
5	6	30	0	3
5	7	35	5	3
5	8	40	0	4
5	9	45	5	4
5	10	50	0	5

6	0	0	0	0
6	1	6	6	0
6	2	12	2	1
6	3	18	8	1
6	4	24	4	2
6	5	30	0	3
6	6	36	6	3
6	7	42	2	4
6	8	48	8	4
6	9	54	4	5
6	10	60	0	6

7	0	0	0	0
7	1	7	7	0
7	2	14	4	1
7	3	21	1	2
7	4	28	8	2
7	5	35	5	3
7	6	42	2	4
7	7	49	9	4
7	8	56	6	5
7	9	63	3	6
7	10	70	0	7

8	0	0	0	0
8	1	8	8	0
8	2	16	6	1
8	3	24	4	2
8	4	32	2	3
8	5	40	0	4
8	6	48	8	4
8	7	56	6	5
8	8	64	4	6
8	9	72	2	7
8	10	80	0	8

9	0	0	0	0
9	1	9	9	0
9	2	18	8	1
9	3	27	7	2
9	4	36	6	3
9	5	45	5	4
9	6	54	4	5
9	7	63	3	6
9	8	72	2	7
9	9	81	1	8
9	10	90	0	9
``````

Giovanni
Posted on 2002-05-12 05:09:44 by sch.jnn
Ciao Giovanni,

The stack size is no problem. In other threads I explained how to "free " it.

BTW: in a post in this thread I expressed some doubts concerning the practical difficulties once you go into giant numbers, do they apply also to your method?
Posted on 2002-05-12 08:24:27 by Maverick
you cant only trust on patterns ... you must prove it

look at 11

11^0 - = 1
11^ 2 = 121
11^ 3= 1331
11^4 = 16461

you see here a pattern? looks like pascal's tringle,doesnt it ?

but when you keep on calc .. 11^5 destories the pattern

if you think you have a pattern .. it can be right for all the numbers , it can be right for big part of the numbers and maybe even be true for only small part of numbers

bye

eko

EDIT:
you should take a look in http://www.geocities.com/~harveyh/primes.htm
Posted on 2002-05-12 08:49:41 by eko
Giovanni, how is it that you are able to say a guess is good when there are 40 possiblities for two digits decimal? Everyone of them is a valid! eko is absolutely correct - the patterns are merely clues to possible algorithms. For example, in the case of binary (RSA-576) the carries in the center can add up to 87 - effecting 6 bits forward. I can see ways to reduce the guessing for runs of 0's or 1's, but this method needs to be combined with something else to be effective.

eko, nice link - one of my favorites.
Posted on 2002-05-12 10:47:38 by bitRAKE
eko, the 11^x things is pascals triangle. You just need a higher base than 10 to see it for values above 4.
Posted on 2002-05-12 12:09:18 by Eóin
realy?
:eek:

give me an example? which base?

bye

eko
Posted on 2002-05-12 14:38:45 by eko
eko:

Try hex values instead of decimals. Of course you need 11hex, not 11dec in hex (B):
``````
11^0=1
11^1=11
11^2=121
11^3=1331
11^4=14641
11^5=15AA51
``````

--

I didn't have a chance to read through this thread as I've been away for a while and this thread is quite long :).
It's very interesting... I couldn't really follow the 10147 example Giovanni showed but like Maverick it makes me wonder how much work is needed to do larger numbers.

Thomas
Posted on 2002-05-12 14:52:54 by Thomas
well its nice. . 11h ?
how far can i get with this ??
but still .. its not 11 prime .. its 17 prime ..
so have you changed everything .

but realy nice shoud c how far i can get .

bye

eko
Posted on 2002-05-12 15:05:06 by eko

... it makes me wonder how much work is needed to do larger numbers.

A lot. The 576 sample takes about 500 sheets of paper and 3 ball-pens, based on loose estimates :)

Giovanni
Posted on 2002-05-12 15:28:52 by sch.jnn
The 576 sample takes about 500 sheets of paper and 3 ball-pens, based on loose estimates

Well, I've got the ball-pens. I've got the sheets of paper.
Now I just need to know how to solve the 576 sample. :)

S3nf

P.S.: Time is on my side. :grin:
Posted on 2002-05-12 15:58:54 by S3nf