1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Does a formula exist?

  1. Jul 18, 2013 #1
    I've been looking into prime number factorisation and was wondering does a formula actually exist or is it thought to be impossible to factor primes using a formula and they need to be factored using brute force?
    [/PLAIN] [Broken]
    RSA Algorithm
    Last edited by a moderator: May 6, 2017
  2. jcsd
  3. Jul 18, 2013 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper

    Maybe the OP is talking about taking an arbitrarily large number N and finding all of its prime factors. I think the terminology 'prime number factorisation' is somewhat confusing.

    For instance, 12 = 2*2*3
  4. Jul 18, 2013 #3
    Yes that is what I'm talking about, sorry for the confusion

    "The most difficult integers to factor in practice using existing algorithms are those that are products of two large primes of similar size, and for this reason these are the integers used in cryptographic applications."

  5. Jul 18, 2013 #4
    Yes, algorithms for factoring numbers into primes exist. But they're not very fast. Currently, it is much easier (=faster) to check if something is prime or not than to actually find a primal decomposition.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook