Prime number greater than n

Question

Consider the follwing problem:

Given $n$ (in binary) output a prime number $p \geq n$ (not necessarily the first prime number after $n$)

Are there better techniques than the trivial one that scans $n,n+1,n+2,...$ until a prime is found?

And can we do better if the full factorization of $n$ is given?

Answer 1

A major optimization of your method would be

if n<2**74207281-1:
    return 2**74207281-1
else:
    n=n|1 #makes n odd
    while True:
        if is_prime(n):
            return n
        n+=2

Answer 2

Currently, there is no method known to construct arbitary large prime numbers, so the problem is currently out of reach.

A solution to this problem would be very useful because high rewards have been promised to find large prime numbers.