Finding a coprime of a general magnitude.

Question

I have an arbitrary number $x$. I would like to compute a number that is coprime to $x$ that's close(ish) to the square root of $x$. I don't need to find them all, and factoring $x$ is expensive. I just need one number. I could also check a few primes near the square root of $x$, but computing primes and storing primes is expensive.

Constant time and space, preferably.

Answer 1

Since calculating the gcd of two arbitrary number isn't expensive, you can practically brute force it.

Algorithm:

1. Generate a random number n.
2. Find its integer-square-root r.
3. Check if gcd(n,r)=1. If yes, return r and exit.
4. If no, add 1 to r, and repeat step 3.

Python:

import random
import time
start = time.time()
bit = 512 # even
num = 1
for _ in range(bit): num = num * 2 + random.randrange(2)
end = time.time()
print("random number:")
print(num)
print("time for generating random number:       %f"%(end-start))

# integer square root (wiki)
start = time.time()
res = 0
bit = 2**bit
while bit:
    if num >= res + bit:
        num -= res + bit
        res = (res >> 1) + bit
    else:
        res >>= 1
    bit >>= 2
end = time.time()
print("time for generating itneger square root: %f"%(end-start))

def gcd(a,b):
    while a: a,b = b%a,a
    return b

start = time.time()
while gcd(res,num) != 1: res += 1
end = time.time()
print("time for generating co-prime number:     %f"%(end-start))

print(res)

Does it in fraction of a second.

Try it online!

Sample output:

random number:
16956998685025525617332092680088906859010597516989049974644188276809460728386128015966080402491132114558031760245789600047216269236212122151725198496639367
time for generating random number:       0.000913
time for generating itneger square root: 0.000193
time for generating co-prime number:     0.000031
130219041176878297644835828972023265387463111246248427493495319607240172982284