Finding huge Mersenne primes is (comparatively) easy because there is the Lucas-Lehmer primality test.
For numbers of the form C^N+1 where C is factored (here: 919444 = 2 * 2 * 53 * 4337 and N=2^20) one can try to find a primitive root (of the multiplicative group). In other words, Pratt's primality certificate is doable.
For "random" numbers of this size (random meaning not of some rather special form) proving primality is way out. Still a huge number "surviving" several rounds of the Rabin-Miller (compositeness!) test can safely be assumed to be prime.