Sum of bits of prime factors exceed exponent on M1999

[James Heinrich]

Originally Posted by charybdis

The incorrect figure of 1421.79 bits almost certainly comes from taking the number of digits in the factor, 428, and multiplying it by log2(10).

This is the core of the problem. Both PHP and MySQL log2 functions do not work on numbers larger than 1024 bits, so if I ever need a bitsize value for that I do indeed use strlen($factor) * log(10) / log(2).

There is a separate database table that records the PRP/prime "last factor" for fully-factored numbers which is where most (all?) of the instances of >1024-bit numbers are stored (and read from). If someone knows a better way to calculate log2 for such numbers (either in PHP or possibly some CLI call to an external program) please let me know.

In this case I can most likely go through the 134 affected exponents and properly calculate the last-factor bitsize from the size of all the other factors. I'll post back when I have done so.

edit: the exponents that were off (by more than .01 bits)

M 1,723: should be  1,326.34065 not  1,328.77124 diff: -2.43058
M 1,999: should be  1,418.58406 not  1,421.78522 diff: -3.20117
M 2,029: should be  1,591.37478 not  1,594.52549 diff: -3.15070
M 2,351: should be  1,988.78693 not  1,989.83493 diff: -1.04800
M 2,357: should be  2,151.62368 not  2,152.60941 diff: -0.98573
M 2,441: should be  2,158.51624 not  2,159.25326 diff: -0.73702
M 2,749: should be  2,329.88124 not  2,331.99352 diff: -2.11228
M 2,789: should be  2,334.28500 not  2,335.31545 diff: -1.03045
M 2,887: should be  2,656.76445 not  2,657.54248 diff: -0.77802
M 3,089: should be  2,798.74096 not  2,800.38538 diff: -1.64443
M 3,037: should be  2,841.56270 not  2,843.57045 diff: -2.00775
M 3,203: should be  2,958.40816 not  2,959.83793 diff: -1.42977
M 3,307: should be  2,971.92590 not  2,973.12564 diff: -1.19974
M 3,467: should be  3,150.24549 not  3,152.50976 diff: -2.26428
M 3,413: should be  3,157.52277 not  3,159.15362 diff: -1.63085
M 3,733: should be  3,263.20825 not  3,265.45532 diff: -2.24706
M 3,637: should be  3,320.98003 not  3,321.92809 diff: -0.94806
M 4,021: should be  3,525.91920 not  3,527.88764 diff: -1.96843
M 3,917: should be  3,624.14333 not  3,624.22355 diff: -0.08022
M 4,111: should be  3,928.18026 not  3,929.84094 diff: -1.66068
M 4,349: should be  3,948.44975 not  3,949.77250 diff: -1.32275
M 4,507: should be  4,309.23022 not  4,311.86267 diff: -2.63245
M 5,393: should be  5,010.08307 not  5,012.78950 diff: -2.70643
M 7,013: should be  6,486.79244 not  6,487.72557 diff: -0.93313
M 6,679: should be  6,501.25682 not  6,504.33521 diff: -3.07839
M 7,669: should be  7,450.80075 not  7,451.08472 diff: -0.28397
M 8,233: should be  7,951.92887 not  7,952.69586 diff: -0.76699
M15,359: should be 15,146.96351 not 15,147.99211 diff: -1.02861
M22,193: should be 21,995.55279 not 21,997.80784 diff: -2.25506
M32,611: should be 32,341.32470 not 32,342.29193 diff: -0.96724
M51,487: should be 51,337.52372 not 51,340.39871 diff: -2.87499
M82,939: should be 82,839.52114 not 82,842.24283 diff: -2.72169
M84,211: should be 84,014.52029 not 84,014.88345 diff: -0.36315

[James Heinrich]

I have corrected the 33 affected exponents, and updated the bit of code where these slightly-off bitsize values for PRP cofactors is entering the database to automatically look up the correct bitsize value when a new large value is entered.

Thanks for letting me know.

[R. Gerbicz]

Originally Posted by James Heinrich

There is a separate database table that records the PRP/prime "last factor" for fully-factored numbers which is where most (all?) of the instances of >1024-bit numbers are stored (and read from). If someone knows a better way to calculate log2 for such numbers (either in PHP or possibly some CLI call to an external program) please let me know.

In c++:

double getlog2(string s){
	
	int L=s.length();
	
	if(L<=16)
	   return log(stoll(s))/log(2);
	
	return (log(stoll(s.substr(0,16)))+(double)(L-16)*log(10))/log(2);
}

You can write this with a single return s.length()<=16? : ; routine, not wanted to hide/collapse everything.
Make sure that in your language it is working also on the 10-16 string length, otherwise maybe write everywhere 9 instead of 16 [you'll get slightly larger error in the log2 computation]..