Thread: Finding prime factors

  1. #1
    Veni Vidi Vice
    Join Date
    Aug 2001
    Posts
    343

    Finding prime factors

    Hiho,

    I'm doing this Computer Security project with ElGamal encryption.
    Thing is I need to produce a generator for my prime to be able to continue with encoding, and to produce one I need prime factors of my (prime number - 1) ( which can be up to 32 bits long ).
    Anyone who can help me on this ?
    Any help would be appreciated!
    Thanks in advance !

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    Seeing as how we aren't going to do your job for you, what do you have so far? When you post questions like this if seems very much like you haven't even tried to solve the problem. We find that attitude repulsive, so it's a good idea to tell us what you've tried, what's not working right, what you think may be wrong, and code or at the very least a design.

    -Prelude
    My best code is written with the delete key.

  3. #3
    Registered User
    Join Date
    May 2002
    Posts
    50
    While the above posters are correct, this is something you should research on your own, I will recognize that using even Google will yield difficulties in finding what you're looking for...

    See, here is the difference between computer PROGRAMMING and computer SCIENCE. Programming means just writing the program and using some algorithm that either you come up with yourself, or you find in a book. The programmer will just cut and paste what they need and understand the rudiment of it, but not the source - and so will be limited in how well they can use it.

    The computer SCIENTIST will understand the mathematical nature of the algorithm necessary to solve the problem. You're asking a problem solved by discrete mathematics, and you wouldn't know how to do what you're asking unless you have taken discrete math courses and have some knowledge of computer SCIENCE not computer PROGRAMMING.

    While I don't know how to write the syntax in C, here is the math behind what you're asking:

    The prime factors of any number will be less than or equal to sqrt(n) where n is an integer. This doesn't help if you have an integer like 138657984168491685567464653816851. You would have to test primality for every single number between 2 and sqrt(n).

    Since you're using encryption, my guess is you're using numbers on that size. If you're using much smaller numbers whose factors you can quickly compute, it's an easy matter to find the factors of each number from 2 to n and see if there are any that aren't 1 or n. I don't know how efficiently C can do this, but LISP based languages can do it VERY quickly.

    So far I haven't said anything that will help you.

    Here is the mathematical basis of something that might help:

    Consider the problem of finding the prime factorization of n. Begin by dividing n by successive primes, starting with the smallest prime, 2. If n has a prime factor, then the prime factor p not exceeding sqrt(n) will be found. Continue by factoring n/p. Now, n/p has no prime factors exceeding sqrt(n/p). If you find a prime factor q, then continue by factoring sqrt(n/(pq)). This procedure is continued until the factorization has been reduced to a prime. Here is an example:

    7007/2 is not an integer.
    7007/3 is not.
    7007/5 is not.

    7007/7 = 1001. So n=7007, p=7.

    1001/7 = 143. So n=7007, p=7, q=7.

    143/7 is not an integer.

    143/11 = 13. 13 is prime, and we're done. The net result is:

    7007= 7*7*11*13

    = 7^2 * 11 * 13

    This is a huge project. Encryption and prime factorization are very deep, very important issues and are being 128-bit encryption, almost ALL internet security, hashing, data storage, data security, etc. You might want to find yourself someone experienced in this to help you. The answer isn't as simple as an algorithm.

  4. #4
    Registered User
    Join Date
    May 2002
    Posts
    50
    As a testament to what I said before, this was somewhat difficult to find but seems to be what you're looking for....

    In case you don't know, the expression

    p-1|q means that q is divisible by p-1.

    x (mod y) is x modulus y, an expression denoting the remainder of dividing x by y.

    The triple equals sign means concurrency and means that that the value on the left hand side of the concurrancy has the same remainder when divided by y as x does.

    Hope this helps

    Go here for some help

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 3
    Last Post: 02-19-2009, 10:32 PM
  2. Replies: 3
    Last Post: 03-29-2005, 04:24 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Finding and Printing prime numbers using arrays
    By Sektor in forum C++ Programming
    Replies: 5
    Last Post: 12-11-2003, 08:29 PM