Finding the square root of a large mersenne number

[Fusion_power]

I am trying to figure out how long it would take to find the square root of say a 10 million digit number. I am currently testing exponent 33,349,067. What would be the fastest code method of determining the square root? I think I can show this in math pseudo better than I can explain it.

(a 10 million digit number) q = (2^33349067-1)
(the square root of q) srq = sqrt (q)
(the remainder after subtracting the square from the number) rmd = q - (srq^2)

My interest is based on the current method of trial factoring. If I have the math down correctly, the number of potential factors of a Mersenne number is severely limited. Would a squares based algorithm potentially use fewer steps to find factors than the current method shown on http://www.mersenne.org/math.htm ?

Thanks,

Fusion

[Joe O]

A good first approximation to sqrt(2^33349067-1) would be 1.414*2^166724533

[Joe O]

A good first approximation to sqrt(2^33349067-1) would be 1.414*2^16674533

Why can't we edit posts in this forum?

[tom11784]

they've disabled editting for regular users to try to deal with speed issues from what i understand

[Xyzzy]

Yes, please check the message preview before you commit! :)

[cheesehead]

Originally Posted by Fusion_power

My interest is based on the current method of trial factoring. If I have the math down correctly, the number of potential factors of a Mersenne number is severely limited. Would a squares based algorithm potentially use fewer steps to find factors than the current method shown on http://www.mersenne.org/math.htm ?

Are you speaking, perhaps, of "Fermat's factoring method" or "Kraitchik's method"? Fermat's method tries to find two numbers whose squares differ by a multiple of the number to be factored. Kraitchik found a way to speed up Fermat's method. See Math 511, Fermat's Factoring Method at http://www.math.ksu.edu/math511/notes/925.html

[Fusion_power]

Cheesehead,

Yes, but no. Fermat understood something important about finding the factorization of a number. What he did was organize a number into a matrix then analyze the matrix for its prime constituents. In its current implementation it would be useless on mersenne numbers.

I think a mersenne specific optimization could be coded. Thats the reason I am trying to figure out the time required to find the square root of a very large number.

What would qualify as a mersenne specific optimization? To start with it would only permit factors of the form 2kp+1.

Fusion

[tom11784]

factors can only be congruent to 1 or 7 mod 8

[xilman]

Originally Posted by Fusion_power

Cheesehead,

Yes, but no. Fermat understood something important about finding the factorization of a number. What he did was organize a number into a matrix then analyze the matrix for its prime constituents. In its current implementation it would be useless on mersenne numbers.

I think a mersenne specific optimization could be coded. Thats the reason I am trying to figure out the time required to find the square root of a very large number.

What would qualify as a mersenne specific optimization? To start with it would only permit factors of the form 2kp+1.

Fusion

It is extremely unlikely that this method would work for Mersenne numbers. You are describing Fermat's method, admittedly sped up by a factor of (2kp+1) or more, but unless the factors are very close together (i.e. unless they differ by at most a few times the 4th root of the number you are trying to factor) Fermat's method will not find the factors in a reasonable time.

Try implementing it, by all means, but test it on small Mp first. You will find it useless for p as small as 500, where we can already factor Mersenne numbers by other algorithms. The run time get worse, much worse, as p increases.


Paul

[apocalypse]

Fusion_power -

Here's a fairly straightforward square root algorithm I wrote for the java.math.BigInteger class as it doesn't have one already...

I'm sure there are faster algorithms, but this one is quadratic, which isn't too bad.

[code:1]
public BigInteger sqrt(BigInteger n) {
int currBit = n.bitLength() / 2;

BigInteger remainder = n;
BigInteger currSquared = BigInteger.ZERO.setBit(2*currBit);

BigInteger temp = BigInteger.ZERO;
BigInteger toReturn = BigInteger.ZERO;

BigInteger potentialIncrement;
do {
temp = toReturn.setBit(currBit);
potentialIncrement = currSquared.add(toReturn.shiftLeft(currBit+1));

int cmp = potentialIncrement.compareTo(remainder);
if (cmp < 0) {
toReturn = temp;
remainder = remainder.subtract(potentialIncrement);
}
else if (cmp == 0) {
return temp;
}
currBit--;
currSquared = currSquared.shiftRight(2);
} while (currBit >= 0);
return toReturn;
}
[/code:1]

Some timings:
[code:1]
2^33349 - 1
sqrt takes 1109 ms

2^333490 - 1
sqrt takes 161891 ms
[/code:1]
on my Athlon XP, which extrapolates to 6-7 weeks for 2^33349067 - 1, so I would recommend finding a better sqrt algorithm.

[Uncwilly]

Could I suggest the old fashioned method?

Get that program that will expand 2^33349067-1 to its decimal equivalent. Then write (I think that I could do it, but don't quote me) and run a simple program that takes the square root the by hand method. The only critical part should be knowing if it has an even or odd number of digits.

Si o No