Finding the aproximate integer Sqrt of a large prime

  • Thread starter Facet
  • Start date
  • #1
2
0
I am trying to understand how I can find the square root of a large prime number in the form of an integer value, the portion after the decimal is irelevant.

The numbers I wish to compute range around 188 multiplied by 3 to the power of 6548 plus 1, as an example. so lets say in excess of 3000 digits.

My problem with this is, using my quad-core machine, I'm finding my petty division through subtraction routine fairly slow, and (x+a/x)/2 as a solution is failing badly.

Can someone please find time to discuss with me a way of doing this?

Can a prime have a GCD with a smaller number(like the sqrt), I somehow just don't see it...

So if there is an easy solution, please let me know it =)
 

Answers and Replies

  • #2
AlephZero
Science Advisor
Homework Helper
6,994
291
You don't need to do any division at all.

Just use (x+k)^2 = x^2 + 2kx + k^2

Call your prime p. Start with x = the largest value of [itex]2^m[/itex] where [itex]x^2 < p[/itex], and [itex]k = x/2[/itex]

Find (x+k)^2. If it is less than p, let x = x+k.
Divide k by 2 and repeat, until k = 1.

If your big arithmetic routines work in decimal not binary, you can use the same sort of algorithm to pick off one decimal digit of the answer at a time.

You don't need to spend time calculatiing the right-hand digits of the numbers that you know are zero, of course.
 
  • #3
2
0
Thankyou for the quick reply, much appreciated.... =)
I really need to touch up on my maths =(
I'm sure what you posted will help me out....
I can straight away see how much faster that would be ;)
one quick question - what is m
Edit: nvm - I think I see what you say =)
 

Related Threads on Finding the aproximate integer Sqrt of a large prime

  • Last Post
Replies
7
Views
5K
  • Last Post
Replies
6
Views
10K
Replies
9
Views
2K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
10
Views
2K
  • Last Post
Replies
12
Views
3K
Replies
1
Views
3K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
3
Views
1K
Top