Factoring algorithm
-
Does anyone have any comment on my factoring algo below: A new method to factor large semi primes. The plan is to factor large semi prime numbers. Start by picking 2 Prime Numbers of appropriate digit size. Choose one as a 200 digit Prime Number, and the other as a 300 digit Prime Number, where their product would be a 500 digit prime number. Then convert the two decimal digit prime numbers to binary values, and multiply them to form the binary semi prime product. Calculate the bit size of the binary product. Save a copy of this semi prime into another value whose bit size is the size of the semi prime rounded up to a DWORD (mod 32 bit) bound, but left shift it until it fills the largest DWORD. Then save another copy of this left shifted semi prime, but this time right shifted by 1 bit. These copies of the semi prime will be used to compare the products of the highest test DWORDS calculated in the algorithm below (see below for the explanation of why two copies are used). The semi prime product would then be factored using a new algorithm. It has been suggested (by S. C. Coutinho in "The Mathemetics of Cipher", Chapter 11) that to select the prime numbers for a key of a digit size of r, select one between a digit size of ((4 / 10) * r) and ((45 / 100) * r). The starting point for the factoring will be chosen as the middle value between these limits, and will step alternately higher and lower until the factors are discovered. The first starting factor will then be the p (the smaller number), and the other starting factor will be q (the larger number) which will be set to ((10^r ) / p). With an r of 500, the lowest limit (in digits) will be: p = ((4 / 10) * r) p = ((4 / 10) * 500) p = (4 * 50) p = 200 digits The upper limit will be: p = ((45 / 100) * r) p = ((45 / 100) * 500) p = (45 * 5) p = 225 digits The mid-point will be: P = ((200 + 225) / 2) p = 212 digits Thus the starting p is a 212 digit number. The other starting factor will be: q = ((10^r) / p) q = ((10^500) / (10^212)) q = 288 digits The p value is then the calculated digit size (converted to bits and then DWORDS), but the q value must be calculated by subtracting the selected p value bit size from the selected semi prime bit size (and then rounded up to DWORDS). These bit sizes define bit fields that will be filled in from both ends with actual values during the factoring process. The bit size,
-
Does anyone have any comment on my factoring algo below: A new method to factor large semi primes. The plan is to factor large semi prime numbers. Start by picking 2 Prime Numbers of appropriate digit size. Choose one as a 200 digit Prime Number, and the other as a 300 digit Prime Number, where their product would be a 500 digit prime number. Then convert the two decimal digit prime numbers to binary values, and multiply them to form the binary semi prime product. Calculate the bit size of the binary product. Save a copy of this semi prime into another value whose bit size is the size of the semi prime rounded up to a DWORD (mod 32 bit) bound, but left shift it until it fills the largest DWORD. Then save another copy of this left shifted semi prime, but this time right shifted by 1 bit. These copies of the semi prime will be used to compare the products of the highest test DWORDS calculated in the algorithm below (see below for the explanation of why two copies are used). The semi prime product would then be factored using a new algorithm. It has been suggested (by S. C. Coutinho in "The Mathemetics of Cipher", Chapter 11) that to select the prime numbers for a key of a digit size of r, select one between a digit size of ((4 / 10) * r) and ((45 / 100) * r). The starting point for the factoring will be chosen as the middle value between these limits, and will step alternately higher and lower until the factors are discovered. The first starting factor will then be the p (the smaller number), and the other starting factor will be q (the larger number) which will be set to ((10^r ) / p). With an r of 500, the lowest limit (in digits) will be: p = ((4 / 10) * r) p = ((4 / 10) * 500) p = (4 * 50) p = 200 digits The upper limit will be: p = ((45 / 100) * r) p = ((45 / 100) * 500) p = (45 * 5) p = 225 digits The mid-point will be: P = ((200 + 225) / 2) p = 212 digits Thus the starting p is a 212 digit number. The other starting factor will be: q = ((10^r) / p) q = ((10^500) / (10^212)) q = 288 digits The p value is then the calculated digit size (converted to bits and then DWORDS), but the q value must be calculated by subtracting the selected p value bit size from the selected semi prime bit size (and then rounded up to DWORDS). These bit sizes define bit fields that will be filled in from both ends with actual values during the factoring process. The bit size,
That's bigger than the common homework questions here. Is it for your thesis?
-
That's bigger than the common homework questions here. Is it for your thesis?
Bernhard, No this is not for any homework assignment. It is just an attempt to find another algorithm for factoring numbers - primarily to factor a semi prime. I know that this will be Big Data, but before I start implementing, is there any problem within the algorithm itself? Dave.
-
That's bigger than the common homework questions here. Is it for your thesis?
Maybe not thesis but can be a good resource - http://www.codeproject.com/Insider.aspx/undefined/?fid=1658735&tid=4791393[^]
I'm not questioning your powers of observation; I'm merely remarking upon the paradox of asking a masked man who he is. (V)
-
Does anyone have any comment on my factoring algo below: A new method to factor large semi primes. The plan is to factor large semi prime numbers. Start by picking 2 Prime Numbers of appropriate digit size. Choose one as a 200 digit Prime Number, and the other as a 300 digit Prime Number, where their product would be a 500 digit prime number. Then convert the two decimal digit prime numbers to binary values, and multiply them to form the binary semi prime product. Calculate the bit size of the binary product. Save a copy of this semi prime into another value whose bit size is the size of the semi prime rounded up to a DWORD (mod 32 bit) bound, but left shift it until it fills the largest DWORD. Then save another copy of this left shifted semi prime, but this time right shifted by 1 bit. These copies of the semi prime will be used to compare the products of the highest test DWORDS calculated in the algorithm below (see below for the explanation of why two copies are used). The semi prime product would then be factored using a new algorithm. It has been suggested (by S. C. Coutinho in "The Mathemetics of Cipher", Chapter 11) that to select the prime numbers for a key of a digit size of r, select one between a digit size of ((4 / 10) * r) and ((45 / 100) * r). The starting point for the factoring will be chosen as the middle value between these limits, and will step alternately higher and lower until the factors are discovered. The first starting factor will then be the p (the smaller number), and the other starting factor will be q (the larger number) which will be set to ((10^r ) / p). With an r of 500, the lowest limit (in digits) will be: p = ((4 / 10) * r) p = ((4 / 10) * 500) p = (4 * 50) p = 200 digits The upper limit will be: p = ((45 / 100) * r) p = ((45 / 100) * 500) p = (45 * 5) p = 225 digits The mid-point will be: P = ((200 + 225) / 2) p = 212 digits Thus the starting p is a 212 digit number. The other starting factor will be: q = ((10^r) / p) q = ((10^500) / (10^212)) q = 288 digits The p value is then the calculated digit size (converted to bits and then DWORDS), but the q value must be calculated by subtracting the selected p value bit size from the selected semi prime bit size (and then rounded up to DWORDS). These bit sizes define bit fields that will be filled in from both ends with actual values during the factoring process. The bit size,
Member 4194593 wrote:
The third table is just a list of the prime numbers to be considered (all prime numbers
less than 300 decimal digits), but saved in a special way as a multi-level directory
structure as described below.A quick consultation with the revered Dr Riemann indicates that there are over 10^297 primes less than 10^300. Since there are somewhere on the order of 10^80 atoms in the known universe, your compression scheme must achieve a minimum compression ratio in excess of 10^217 : 1. Can't see that happening in a hurry... Sometimes "big data" is just too big. Cheers, Peter
Software rusts. Simon Stephenson, ca 1994. So does this signature. me, 2012
-
Member 4194593 wrote:
The third table is just a list of the prime numbers to be considered (all prime numbers
less than 300 decimal digits), but saved in a special way as a multi-level directory
structure as described below.A quick consultation with the revered Dr Riemann indicates that there are over 10^297 primes less than 10^300. Since there are somewhere on the order of 10^80 atoms in the known universe, your compression scheme must achieve a minimum compression ratio in excess of 10^217 : 1. Can't see that happening in a hurry... Sometimes "big data" is just too big. Cheers, Peter
Software rusts. Simon Stephenson, ca 1994. So does this signature. me, 2012
Peter, I was waiting for someone to figure that out. Check with Ravi, I proposed this to him in Email in March. The following is the second half of the original Email to him. Too bad this would not work, I think that the actual algo would work except for the fact that the file requirements are insane:
------------------------------------------------------------------------------------------
The following discussion is why this algorithm (the part above this point) should be
published in Algorithms on April 1st without this lower section - let the wrecking crew of
experts in CP determine what is so wrong with the solution (the algorithm is correct but
just will not work).
Now, the number of primes with 300 digits is:
((10^300) / ln(10^300)) = (3.33 \* (10^297))The max size of a prime number in that range is 52 DWORDS or 26 QWORDS which would convert
to 232 characters so the total size of all path names describing all of these prime
numbers will be:(232 \* 3.33 \* (10^297)) = (7.7 \* (10^299)) BYTESThe number of terabytes to contain this data would be:
(7.7 \* (10^299) / (10^12)) = (7.7 \* (10^287)) TBThe number of 4 TB drives to contain this total size would thus be:
((1/4) \* 7.7 \* (10^287)) = (1.9 \* (10^287)) drivesI don't think that Seagate has enough material to create that many drives. Penrose in his
book "The Emperor's New Mind" estimated that the number of particles in the visible
universe was 10^80, and after that problem has been solved, you still have another
problem about how much time it would take to write out these prime number directories to
the drives. So much for having the prime numbers available to use as trial multipliers to
see if the product matches the semi prime.Lest you think it would make a difference (in the count and total size of the prime
numbers) if you only saved the prime numbers that lie between 10^200 and 10^300:((10^300) / ln(10^300) - (10^200) / ln(10^200)) = (1.447 \* (10^297) - 2.171 \* (10^197)) = (1.447 \* (10^297)) or (1.447 \* (10^297)) = (1.447 \* (10^297))Saving the number of prime numbers in a range of digits (from 200 to 300) would not even
make a visible dent in the count because the actual calculation is subtracting a 197 digit
number from a 297 digit number, leaving a 297 digit number with a dimin
