Properties of Composites Composed of Two Odd Prime Factors

[Edwin]

I have been working on constructing a method to factor composite numbers composed of two odd prime numbers a and b. As a result, I have been experimenting numerically with various patterns to see if I could find some patterns that would reveal information about composites of two prime numbers that I might use in furthering my progress toward my ultimate goal of constructing a general factoring algorithm that involves solving a system of algebraic equations to factor the composite. I have yet to find a method, but have decided to post what I have so far over the next couple of weeks for others with fresh eyes to take a look at and critique. I will start by laying out a series of theorems in the first post, and then in following posts will elaborate on each theorem and attempt to prove them. Any suggestions, ideas, and questions are most welcome at any time. I also ask for ideas on how I may be able to better present these ideas in ways that would be more effective. Thanks for all of your assistance!



Edwin

Theorem 1)

Every number $$C$$ that is an odd number composed of two prime numbers $$a$$ and $$b$$ such that
$$\begin{gather*}C = a*b\end{gather*}$$
can be written as the sum of n consecutive odd integers.

Theorem 2)

If $$C$$ is an odd number composed of two prime factors $$a$$ and $$b$$, then the number of consecutive odd integers required to add up to $$C$$, is equal to the smaller of the two prime factors of $$C$$.

Theorem 3)

The larger of the two prime factors of $$C$$ is the average to the first and last number in the consecutive sum of odd numbers that add up to $$C$$.

Theorem 4)

If $$C$$ is an odd number that is composed of two prime factors $$a$$ and $$C$$, then there exists atleast one non-arbitrary perfect square that can be used to factor $$C$$ through a finite number of algebraic operations.

Theorem 5)

If $$C$$ is an odd number that is composed of two prime factors $$a$$ and $$b$$, then the non-arbitrary perfect square that can be used to factor $$C$$ via finite number of algebraic operations is the first perfect square acquired by adding a consecutive number of odd integers starting with the number 1 to $$C$$ and is equal to the average of the prime factors of $$C$$ quantity squared.

Example:

77 is a composite $$C$$ composed of prime factors 7 and 11.
77+1 = 78
77+1 +3 = 81

81 is the first perfect square acquired by adding consecutive odd integers to composite number 77, and ((7 + 11)/(2))^2 = 9^2 = 81.

Over the next few posts I will briefly elaborate on each of the above theorems. I will try to do so concisely in a brief post for each of the theorems above that can be read quickly and perceived quickly and clearly.

Best Regards,

Edwin G. Schasteen

 

[CRGreathouse]

Factoring odd semiprimes is the essence of general factoring, in that it's the hardest part in general. Deciding if a number is prime is easy (in P thanks to AKS), finding 'small' factors is easy, but finding large factors is hard.

 

[shmoe]

You're essentially trying to write C=x^2-y^2. This is the basis for many factorization algorithms, though they look for x^2=y^2 mod C with x not congruent to +y or -y mod C. The tricky part is finding a suitable x and y quickly. Yours is a brute force approach that can take a very long time, depending on how close together a and b are.

“A Tale of Two Sieves”, Notices of the AMS 43, no. 12 (1996), 1473–1485 by Pomerance is a nice survey article you might want to look up. It's on the AMS website, you'll have to register to access it I believe.

 

[Edwin]

Thanks for the AMS reference and input! I'll head by the AMS website and check it out. Yes, I've noticed that the farther apart the prime factors are, the longer it takes to find the perfect square. My original hopes when first starting on this attempt was to find a system of algebraic equations that can be solved algebraically for the perfect square, or one of several other pieces of information needed to factor a composite composed of two odd prime numbers. My perception is that it might be possible, but most likely, it may turn out that it is actually impossible to create a general set of algebraic equations can be solved to factor composites in general. I have succeeded in finding a combination of equations that involve both trancendental equations and algebraic equations that, if solved efficiently, would work to factor any number. Unfortunately, transcendental equations can not be solved with any finite number of algebraic operations so I don't presume that that system of equations will be of much use. Never the less, I keep them on file just in case. I'll go and see if I can track down that article, and then on my next post will briefly describe the derivation of the first theorem. Once again, thanks for the reference and inputs Shmoe and CRGreathouse!

Best Regards,

Edwin

 

[Edwin]

Found it! I've gotten about half way through the article so far, and it is a remarkable read! The ideas are flowing at this point...thanks for the reference!

Best Regards,

Edwin

 

[Robokapp]

You want the RSA prize, don't you? me and my friends are working on that too. We created a program that can find the integer factors of a number. it works, only problem is it uses only 7 signiffican figures so we're still very far, but I feel we're getting there. I think I can create a way to use the first digits of one factor to find the second 7 digits of the second.

It will take a while, but maybe it will work.
I'm going to start writing some stuff down right now for it. I'll post what I come up with if anything is worth your attention.

 

[Robokapp]

Okay...I got something. I'm not sure how it will help, but this is what I got:

assuming you want to multiply 23*29 without a calculator:
you'd use this thing I
discovered":
if abcdef*ghijkl you can rewrite it as
(l+10k+100j+1000i+10000h+100000g)(f+10e+100d+1000c+ 10000b+100000a)

SO back to 23*29 yes, you can do 23*30-23...but let's say you can't.

(3+10*2)(9+10*2)

so cross multiply 27+60+180+400=667

so 23*29=667
let's try 23*30-23...690-23=667

I don't know yet how this will help with RSA232 but it's a start. maybe one of you guys can use it somehow.

 

[shmoe]

Robokapp, that's not really any different from the usual way you'd multiply two numbers by hand, except yours is less efficient and takes up more space.

If you are interested in the types of algorithms used to tackle the rsa numbers, you might want to have a look at the Pomerance article above.

It might also be worth pointing out that the rsa numbers fall to a combination of the lastest factoring algorithms (and speedy implementations) and a bundle of computing power. According to http://www.rsasecurity.com/rsalabs/node.asp?id=2964 , RSA-640 took "30 2.2GHz-Opteron-CPU years". Unless you have these kinds of resources as well as the know-how to use is, don't expect to be the first to the next rsa number.

 

[Robokapp]

You're right...it's worthless. i was tryin g to take a look at how numbers bond together in a multiplication. I wonder though...how did they come up with the numbers like RSA680 (?) and not know it's factors? Do they have something that gives them...maybe the rounded up factors?

 

[shmoe]

They do know the factors, or at least they did when they made the list of rsa numbers. Known algorithms for Primality testing are *much* faster than factoring, and can find primes in the 200 digit range without blinking. They would have found suitable primes, multiplied them together and then probably thrown away the primes, they aren't needed to verify a factorization.

Some links that you might find interesting:

http://www.cacr.math.uwaterloo.ca/hac/ "Handbook of Applied Cryptography", by Menzies, van Oorschot, and Vanstone. Specifically chapter 4 gives algorithms for finding primes.

http://www.ams.org/notices/200305/fea-bornemann.pdf "PRIMES is in P: a breakthrough for "Everyman"", Bornemann, Folkmar

http://www.ams.org/bull/2005-42-01/ "It is easy to determine whether a given integer is prime", Andrew Granville

 

[Jameson]

Do many people attempt to factor these numbers?

 

[shmoe]

I'd expect lots of people think "wow big prize for factoring a number" and naively set out with no hopes of success. I don't know how many serious teams there are, you might not hear about the team that put in 28 2.2GHz-Opteron-CPU years worth of computation time only to be beaten to the punch, if such a team exists.

 

[Edwin]

Sure,

I am interested in the RSA challenge numbers as well. I appreciate the book reference! I'll check out those books as well. At this time, I am still studying the paper that your referred earlier! It seems like, according to that pomerance article, there has been a lot of luck using sieve methods over the last 20 years! If two different researchers had such good luck with sieve approach, I figure, why reinvent the wheel? So, I am certainly keeping that concept on the back burner so to speak.


I would like to diverge at this time, and consider trying something a little new, I am going to see if I can apply Green's theorem in some way as to reveal information that might serve to factor a given composite. If I find any patterns, I'll post them, useful or not.

Best Regards,

Edwin

 

[Edwin]

Hello,

I promised I would post if I made any progress.

Over the last couple of days, I was able to derive a function that has absolute maximums at the values of the input variable x, when x is a prime factor of C. The absolute maximum of the function is 2.

C = a*b, where a and b are odd prime factors of C.

The equation is as follows:

cos((pi)*x/2+(pi)*C/(2*x)) - cos(pi*x) = 2

The solutions that make this equation true are
plus and minus C, plus and minus 1, plus and minus the prime factor a, and plus and minus the prime factor b.

I appologize for not using the math tools, I didn't have time tonight. I will come back later this week and clean up the math above just as soon as I have more time.

Since researchers over the last 20 years seems to have had a lot of luck with seive techniques, I am looking at trying to construct some kind of seive method using the equation above. Not sure how efficient it will be, but I look forward to finding out!

Best Regards,

Edwin G. Schasteen





Best Regards,

Edwin