Poll

2 votes (66.66%)
No votes (0%)
No votes (0%)
No votes (0%)
1 vote (33.33%)
No votes (0%)

3 members have voted

gordonm888
gordonm888 
Joined: Feb 18, 2015
  • Threads: 45
  • Posts: 2825
November 11th, 2020 at 7:18:38 PM permalink
Quote: ThatDonGuy

Challenge accepted!

Doesn't your method make the assumption that every nonprime number can be expressed as the difference of two squares?

Try your method with X = 10. What happens?



I should have said that every ODD non prime number can be expressed as the difference of two squares. Even composite numbers are definitely not of the form (n^2 -m^2)

Since odd numbers are the only ones we would really be concerned with, I think that is sufficiently interesting.
Quote: ThatDonGuy


Also, you need to make sure that if you do find two squares, they aren't consecutive, as otherwise one of your factors will be 1.



Excellent point. Example: 8^2-7^2 =15 which has factors (8+7) and (8-7) which isn't very interesting.

So: X = n2 - m2; n>m+1

What is interesting is mathematicians have forever been unable to find a polynomial expression that defines prime numbers. But the above polynomial expression defines all odd numbers that aren't prime.

Quote: ThatDonGuy

Note that every positive odd number can be expressed as the difference of two (consecutive) primes.



You lost me with this comment. The difference between two consecutive primes (ignoring 2) must be an even number. What did you mean to say?
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
gordonm888
gordonm888 
Joined: Feb 18, 2015
  • Threads: 45
  • Posts: 2825
November 11th, 2020 at 8:06:02 PM permalink
Okay, let's continue to assume that you have an integer X and you want to test to see whether there is a solution to

n2 - m2 = X

as a way to find factors of X.

In my last post I used modular arithmetic to develop selection rules so that we don't need to test all values of n and n2 to see if an m2 solution exists. Namely:

1. If X ends in 7 then n cannot have a 0, 2, 3, 5, 7 or 8 as its last digit.
2. If X ends in 1 then n cannot have a 2, 3, 7 or 8 as its last digit.
3. If X ends in 3 then n cannot have a 0, 1, 4, 5, 6 or 8 as its last digit.
4. If X ends in 9 then n cannot have a 1, 4, 6, or 9 as its last digit.

I have just started to look at the last two digits of X.

Basically n2 is congruent with (0, 1, 4, 9, 16, 21, 24, 25, 29, 36, 41, 49, 56, 61 64, 69, 76, 81, 84, 89, 96) mod100.

That is 22 of 100 numbers as residues of mod100.

When the last two digits of X are 07 then n is limited to the following two last digits: 4, 6, 14, 16, 24, 26, 34, 36, 44, 46, 54, 56, 64, 66, 74, 76, 84, 86, 94, 96. Basically, that means that n is limited to ending in 4 or 6! That reduces the possible values of n by 80%!

When the last two digits on X are 17, then n is limited to the following two last digits: 9, 19, 21, 29, 31, 41, 59, 69, 71, 79, 81 and 91. That only 12 numbers out of a possible 100 for the two last digits of n -an 88% reduction in numbers to sieve through.

That's all I've done so far. But it shows that we may be able to look at the last n digits of the number to be factorized and use selection rules to gain very significant efficiencies in terms of reducing the number of values of n that must be sieved through to solve n^2 - m^2 = X.

Update: I just looked at the rules for when the last two digits of X are 27 -and they are identical to the rules when the last two digits of X are 07.
Last edited by: gordonm888 on Nov 11, 2020
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
ThatDonGuy
ThatDonGuy
Joined: Jun 22, 2011
  • Threads: 98
  • Posts: 4639
Thanks for this post from:
gordonm888
November 12th, 2020 at 6:27:20 AM permalink
Quote: gordonm888

You lost me with this comment. The difference between two consecutive primes (ignoring 2) must be an even number. What did you mean to say?


Every positive odd number can be expressed as the difference of the squares of two consecutive numbers.
Simple enough proof: every positive odd number is of the form 2N+1, where N is a nonnegative integer, and (N+1)2 - N2 = 2N+1.
gordonm888
gordonm888 
Joined: Feb 18, 2015
  • Threads: 45
  • Posts: 2825
November 12th, 2020 at 3:58:54 PM permalink
Okay, let's continue to assume that you have an integer X and you want to test to see whether there is a solution to

n2 - m2 = X

as a way to find factors of X which are (n+m) and (n-m)

I have now worked out the rules for the last two digits of X; namely, dependent on the last two digits of X the possible values of n are limited to what is shown in the table below. These means that one can use the last two digits of the number you are trying to factor to speed up the sieve search for a suitable set of (m,n).

Last Two Digits of X
Last Two digits of n
01
x5, 01,49,51,99
03, 23, 43, 63, 83
x2, x8
07, 27, 47, 67, 87
x4, x6
09
x5, 03,47,53,97
11
x0, 06,44,56,94
13, 33, 53, 73, 93
x3, x7
17, 37, 57, 77, 97
x1, x9
19
x0, 12,38,62,88
21
x5, 11,39,61,89
29
x5, 23,27,73,77
31
x0, 16,34,66,84
39
x0, 8,42,58,92
41
x5, 21,29,71,79,
49
x5, 7,43,57,93
51
x0, 24,26,74,76
59
x0, 22,28,72,78
61
x5, 19,31,69,81
69
x5, 13,37,63,87
71
x0, 14,36,64,86
79
x0, 02,48,52,98
81
x5, 09,41,59,91
89
x5, 17,33,67,83
91
x0, 3,47,53,97
99
x0, 18,32,68,82


Lots of symmetry in that table, isn't there?

So for some X the search for a suitable pair of (m,n) will be sped up by 80%, while for other X the search will be faster by 86%.

I think the reason I am so intrigued is because the sieve search can be made more efficient by looking at the last n digits of X.

I mean, in an Erasthosthenes sieve, one knows that numbers ending in 0,2,4,5,6, and 8 are not prime and that numbers whose digits sum to a multiple of 3 are also not prime. So, that even when if you don't have a priori knowledge of which potential divisors are prime, you can readily eliminate about 73% of all numbers as possible divisors to be tested by just looking at the digits. But that's about the end of the efficiency for Erasthosthenes. This method is already eliminating more than 73% and will be even more efficient if we develop rules based on the last 3 digits of X (or 4 or more.)

Of course, my proposed method has some other inefficiencies not common with Erasthosthenes. But let's keep plugging away.
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
gordonm888
gordonm888 
Joined: Feb 18, 2015
  • Threads: 45
  • Posts: 2825
November 13th, 2020 at 10:15:21 AM permalink
I have added an additional column to the table from my last post. I am finding that modular nomenclature is an efficient way to represent the constraints on n.


Last Two Digits of X
Last Two digits of n
Required form of n
01
x5, 01,49,51,99
5(mod10), ±1(mod 50)
03, 23, 43, 63, 83
x2, x8
2, 8(mod10)
07, 27, 47, 67, 87
x4, x6
4, 6(mod10)
09
x5, 03,47,53,97
5(mod10), ±3(mod 50)
11
x0, 06,44,56,94
0(mod10), ±6(mod 50)
13, 33, 53, 73, 93
x3, x7
3,7(mod10)
17, 37, 57, 77, 97
x1, x9
1, 9(mod10)
19
x0, 12,38,62,88
0(mod10), ±12(mod 50)
21
x5, 11,39,61,89
5(mod10), ±11(mod 50)
29
x5, 23,27,73,77
5(mod10), ±23(mod 50)
31
x0, 16,34,66,84
0(mod10), ±16(mod 50)
39
x0, 8,42,58,92
0(mod10), ±8(mod 50)
41
x5, 21,29,71,79,
5(mod10), ±21(mod 50)
49
x5, 7,43,57,93
5(mod10), ±7(mod 50)
51
x0, 24,26,74,76
0(mod10), ±24(mod 50)
59
x0, 22,28,72,78
0(mod10), ±22(mod 50)
61
x5, 19,31,69,81
5(mod10), ±19(mod 50)
69
x5, 13,37,63,87
5(mod10), ±13(mod 50)
71
x0, 14,36,64,86
0(mod10), ±14(mod 50)
79
x0, 02,48,52,98
0(mod10), ±2(mod 50)
81
x5, 09,41,59,91
5(mod10), ±9(mod 50)
89
x5, 17,33,67,83
5(mod10), ±17(mod 50)
91
x0, 3,47,53,97
0(mod10), ±3(mod 50)
99
x0, 18,32,68,82
0(mod10), ±18(mod 50)
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
gordonm888
gordonm888 
Joined: Feb 18, 2015
  • Threads: 45
  • Posts: 2825
November 13th, 2020 at 1:02:25 PM permalink
Well, I see that I have taken a wrong turn. I should be searching for values of m rather than values of n.

Again, the basic idea is, for a given integer X to search for values of (m,n) that satisfy X=n2 - m2; n-m >1 because that means that (n+m) and (n-m) are factors of X.

Now obviously n2 > X and n2 > m2 but is m2 < X? If m<sqrt(X) then searching for m between 0 and sqrt(X) will be sufficient to find m.

Ex: 10002 - 9892 = 21 879 and sqrt(21879) ~ 147.92. Here m=989 >147.92 so searching for m between 0 and sqrt(X) is not going to find this value of m.

However, 21 879 = 3*3*11*13*17 and thus will have many sets of (m,n) that satisfy X=n2 - m2; n-m >1. This is because we can combine the prime factors in different ways to make multiple values of (m+n,m-n). For example, 21 879 = 1602 - 612 and also 1522 - 352. And both of those (m,n) pairs have an m< sqrt(X).

What if X is a semiprime, i.e., a product of only two prime factors? Then there will only be one (m,n) pair that satisfies X=n2 - m2; n-m >1. And I think I have convinced myself that in case of a semiprime X that m< sqrt(X). And if that is the case then any X with many prime factors must also have one or more (m,n) pairs where m < sqrt(X).

Thus we can restrict ourselves to the range 0 to sqrt(x) when looking for at least one suitable m that solves our equation. And that should be an easier task than looking for n in the range of numbers greater than sqrt(X)!

The selection rules for searching for m are closely related to the rules for searching for n, but are not the same. They will likely involve the same efficiencies though. But I will need to recalculate new rules.
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
gordonm888
gordonm888 
Joined: Feb 18, 2015
  • Threads: 45
  • Posts: 2825
November 16th, 2020 at 4:11:28 PM permalink
The main method that I have been 'discovering' here is already well established in number theory. Looking for solutions to n=X2 - Y2 as a way to factor n is called Fermat's Factorization method Then, using one of several different approaches with modular arithmetic to make the search more efficient is the "conguence of squares" method. Congruence_of_squares or Dixon's_factorization_method or a variant of Dixon's method called the Quadratic Sieve Quadratic_sieve.

The method I have been using with modular arithmetic appears to be different in it specific aspects than any of these other methods, but may wind up effectively being either the Dixon method or the Quadratic Sieve (QS) method. The QS method was the fastest method for factorization of large numbers up until the early 1990's when the Number Field Factorization method was developed and shown to be faster. The QS method is still the second fastest factorization method for large numbers.

As I've said, I've never had a course in number theory so I often discover things that turn out to be well known. This idea was not a dumb idea, I'm just not the first to think of it, lol.
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.

  • Jump to: