Are there any known techniques for quickly finding a composite number with at least one large prime factor?

Being aware that the above might sound vague. Let's say quickly is anything less than O(n) complexity, and large factor as anything greater than sqrt(C) ,where C is the composite.

To be clear, I don't need to know what the prime factor is, instead I only need to know that the chosen composite contains a large prime factor.

I recall perusing properties of binomial coefficients with respect to the above, but I can't seem to find it.

  • $\begingroup$ Any even number $C$ has a factor $C/2 > \sqrt{C}$ when $C$ is larger than 4 $\endgroup$ – Slugger Jun 18 '16 at 19:38
  • $\begingroup$ Oops, I missed the prime factor part. Thanks for spotting that. $\endgroup$ – niobe Jun 18 '16 at 19:45
  • 1
    $\begingroup$ What do you mean by large? Are you talking about 100 digits, a million digits? $\endgroup$ – almagest Jun 18 '16 at 19:52
  • $\begingroup$ @almagest In my original post I did clarify that the prime factor be greater than sqrt(C), where C is the composite. $\endgroup$ – niobe Jun 18 '16 at 19:56
  • $\begingroup$ @niobe Fine I understand that part. But how big is $n$? I ask because you can get large primes, composites with large prime factors etc as fast as you can type by using a package like Mathematica, but only up to a certain limit on size. I am trying to get an idea of how big you want to go. $\endgroup$ – almagest Jun 18 '16 at 20:00

The usual method is: find two large primes, and multiply them together. This has the great advantage that you are working with numbers approximately half the number of digits compared to your final composite number.

If you want to "happen upon" such a number rather than constructing it, you might try a large Mersenne number $M_p = 2^p -1, p$ prime, check that it's composite using Miller-Rabin, then trial divide by $q=2kp+1$ (hopefully finding nothing) until you are satisfied that the remaining factors are big enough.

  • $\begingroup$ Of course, that is the most straightforward approach, but I was looking for something other than that. $\endgroup$ – niobe Jun 18 '16 at 19:46
  • $\begingroup$ @niobe ... or a large prime and a medium-size prime, if you prefer :-) $\endgroup$ – Joffan Jun 18 '16 at 19:48
  • $\begingroup$ .Perhaps I should ask then, how do I find such a composite without knowing its large prime factor? $\endgroup$ – niobe Jun 18 '16 at 19:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.