Updated Synchronized remainders:
I previously posted some research concerning this topic on 21 May 2021 on this forum. I knew very little at the time and the way I posted my findings was, by one person's comments, unreadable. You can see it at: Where in the math literature is Synchronized remainders?
I know more but the research is still incomplete. I hope the reader will find this post more concise and readable.
Just to say: I do this kind of research to find meaningful relationships between factors. My aim is to find a formulation to factorize Large integer composites, such as the RSA challenge numbers, in polynomial time. Last I checked, there were over 30 challenge numbers still to be factorized. The most recently factorized challenge number RSA768 was not a breakthrough.
I currently have an alternate way to find modular inverses using a formulation that is 30 times slower tan the Extended Euclidean algorithm. A rendition of the Extended Euclidean algorithm executes the modular inverse for a set of numbers that are 308 and 309 digits long respectively in less than 2 seconds. My alternate algorithm takes over a minute. I am hoping that the extra data points generated by my alternate algorithm will advance my research. In fact, I originally called it consecutive multiples and later found out that the math community calls modular inverses.
I self published the derivation of my consecutive multiples algorithm at: https://www.scribd.com/document/502058203/Factorization-Part-3
If you are keen to read it then note that this document is 49 pages long and over 10000 words. Also note that this is part 3 in series of related documents. The previous 2 are also long but very basic. You can find them on my scribd account at: https://www.scribd.com/lists/24209280
For me at least, some interesting findings is linking modular inverses to triangular numbers and contiguous sums.
To begin then...
Let two integers be co-prime. Call them f1 and f2. f2 is odd and f1 is any number from 2 to f2-1.
Search for an m such that: m.f1 mod f2 = m.f2 mod f1
Not proven for all f1 but by searching I cannot find any f1 that does not have an m value. That said, searching for m falls into 3 sets:
Set (a) When f1.f2 mod (f1 + f2) is > f2 then m is the quotient + 1 from dividing f1.f2 by f1 + f2. For example with f1=467 and f2=651 then 304017 / 1118 = a quotient of 271 and a remainder of 1039. Since the remainder of 1039 is > f2 of 651 m is 271 + 1 = 272. It is that simple. The synchronized remainder, is f1+f2 - f1.f2 mod (f1 + f2). In the present example this is 1118 - 1039 = 79
Set (b) Conditionally when f1.f2 mod (f1 + f2) is < f2.
The remainder from f1.f2 mod (f1 + f2) will be called r.
Step 1: Calculate r
Step 2: Using r, calculate the quotient from f2 / r. Lets call this Qf2
Step 3: Calculate the multiple of f1.f2 by adding 1 to Qf2. Lets call this multiple x
Step 4: Compute x.f1.f2. / (f1 + f2). m is, as in set a), the quotient plus 1.
This only works conditionally. The conditions are two properties derived from two calculations:
compute f2 / r: The quotient is called Qf2 the remainder is called Rf2
compute (f1+f2) / r The quotient is called Qs the remainder is called Rs
Property 1: Qf2 <> Qs
Property 2: Rs - Rf2 <> f1
Examples using 4049 as f2:
With f1 = 3634 r is calculated to be 1121 but the following f1s also have r of 1121:
285
1073
2353
2452
3517
From this list of 5 f1s for all except 285 you can use the 4 steps to find m. For all these f1s you can verify that Qf2 <> Qs and that Rs - Rfs <> f1. There is an additional property to note: In step 3, f1.f2.(Qf2+1) / (f1 + f2) all yield the same remainder 4484 and this is the remainder for f1 = 3634 (the highest f1 in the subset)
As for f1 = 285 the 4 steps don't work because the conditions concerning Qf2 and Rf2 are now true. That is to say: Qf2 = Qs and Rs - Rf2 = f1. Because the conditions are not right you now have to incrementally search for x (that is, the correct multiple of f1.f2). Previously, when the conditions were right x is calculated from dividing f2 by r and adding 1 to the quotient. For f1 = 285 The x is found, by searching, to be 23 and 23.f1.f2 mod (f1 + f2) does not equal 4484 but it equals 4113.
Last note: I tested with large numbers that are hundreds of digits long and the 3 steps formulation does work under the right conditions.
Set (c): Set (c) are numbers, like f1 = 285 in the above example. I am currently investigating patterns to find m in these instances but I want to do it in a formulation and not by incremented searching.
I am posting this research here to ask if other have already computed synchronized remainders and if so by what formulation. Speed matters but in these days, I care more about the difference in formulation than the speed of the formulation. I want the data points.
Ultimately the goal is to speed up large integer factorization.
From the perspective of factorization f1 can be a factor in large binary composite such as an un-factorized RSA challenge number where f1 = RSA number / f2, where f2 is the larger of the two prime factors that make up the RSA challenge number.
As can be seen above there is a set of numbers that can yield f1 in an alternate manner, using the subtraction of remainders. How useful will this be? I cannot say. Maybe it is a dead end or maybe it is small piece in a bigger puzzle.