   prime factors
  hello.. can anyone explain further the idea of those algorithms (one of them)??http://en.wikipedia.org/wiki/Quadratic_sievehttp://en.wikipedia.org/wiki/General_number_field_sievewhat i want to do in my project is to check if a number is B-smooth..and i am looking for the fastest algorithm in finding prim factors..   
  If you don't have a more specific question, it will be hard to do a better job of describing the algorithms than what's on Wikipedia.How big are the numbers you will check for B-smoothness? And how big is B?   ;  well the number are big enough.. the project is the following:find the B-smooth numbers between i and j, and the some testcases that it will be tested are:B=1024, i=1, j=1.000.000B=1024, i=1, j=100.000.000B=1024, i=1, j=1.000.000.000i don't want the code here.. what i want is to understand what these methods do.. cause the links above seem rather complicated.. and i need a better explanation..thanks..   ;  There is no one simple fastest algorithm. Different algorithms are better than others for certain ranges of number (or numbers of a specific form like the Mersennes). You'll also take a different approach if you need a list of primes, as opposed to just testing one.Also, these algorithms aren't for finding if a number is prime, they're for factoring large composite numbers. Depending on your needs, there's a number of not guaranteed (but VERY statistically likely) primality tests like the Miller Rabin. The GMP library for C/C++ has this implemented as a function.Anyways, the Quadratic Sieve in layman's terms:All numbers you want to factor for are odd. If they're even, well that's easy. A nice property of odd composite numbers is that their two factors (A,B) are odd. Since they're both odd, they're guaranteed to have a whole number average (adding two odd numbers together always produces an even number). Thus you can represent the factors as (M+D)(M-D), which expanded out is M^2 - D^2. M^2 - D^2 = number->M^2 - number = D^2So the first step is understanding what you want to do. You know the number, so basically you can start at M = ceil(sqrt(number)) and subtract the number. Is it a square? Great. You've just found the factors of the number.That's not the Quadratic Sieve. The Quadratic Sieve builds off of that. It's been proven (it's kinda unimportant to know how) that not only does M^2 - number = D^2 provide factors, but so does M^2 % number = D^2. So let's do a quick example. The number we're trying to factor is 15. For some reason we missed M=4 as a solution. Now we're testing 7. 49-15 is 34, not a square. 49%15 though is 4, which is square. 7+-sqrt(4) is 9 and 5, which you can GCD with 15 to get your answer.Again, that's not the Quadratic Sieve.The Quadratic Sieve builds off of that. The trick it uses is that any square times another is yet a 3rd square. 4*9 = 6*6 for example. What the QS does is take the 'partial' answers, that is the times when M^2 % number is a smallish result, and tries to combine them. If you have a M where M^2 % number is 3, and another M where it is 27, then trying (M1*M2)^2 % number should yield 81. Since 81 is a square, you'll have found your solution.Practically, what it does is build a list of a bunch small primes. Then it tries different M's. If the result can be completely factored by the small primes, (and isn't a square) then the QS keeps it. Once the QS has enough results (the size of the prime list), it stops testing M's and starts multiplying the results together to eliminate non-square factors to eventually get a result. Sometimes the result is the number times 1, which is... kinda useless. Then you get more results until you find one that comes out good. The number field sieve does the same sort of thing, only instead of testing individual numbers to come out with a square, it tests algebraic rings, and is beyond my education/capability to understand.   ;  If you just need to find the small prime factors, trial division is not a bad algorithm. Did you try it? Is it not fast enough?   ;  well yes, it takes much more time than i want.. let me ask you something.. i want to check if a number is B-smooth.. what i have to do is: find the prime factors and check if the largest of them is <= B.. so the goal is to find the largest prime factor.. right???can i do it with quadratic sieve?? cause i think i'll try to do it with that algorithm and not with trial division..   ;Quote:Original post by ghostrider_well yes, it takes much more time than i want.. let me ask you something.. i want to check if a number is B-smooth.. what i have to do is: find the prime factors and check if the largest of them is <= B.. so the goal is to find the largest prime factor.. right???No, you don't have to find all the prime factors. For instance, you can divide your number as many times as you can by the prime numbers up to B. The number is B-smooth if and only if the result of this procedure is 1.Quote:can i do it with quadratic sieve?? cause i think i'll try to do it with that algorithm and not with trial division..Yes, you can do it with a quadratic sieve, but something tells me you are just not understanding the big picture here.Numbers with only small prime factors are easy to factorize, by trial division. Numbers that only have one large prime factor are still easy to factorize, if you stop your trial division when the left over is prime (which can be checked quickly with the probabilistic Miller-Rabin test).There's an algorithm called "Pollard's rho" which works well with numbers that have moderately large prime factors.If you have more than one large prime number then things get tricky, and this is when you have to complicate things enormously and use something like quadratic sieves. But using this to find out if a number is 1024-smooth is "killing flies with cannons", as the Spanish saying goes.;Quote:Original post by ghostrider_well the number are big enough.. the project is the following:find the B-smooth numbers between i and j, and the some testcases that it will be tested are:B=1024, i=1, j=1.000.000B=1024, i=1, j=100.000.000B=1024, i=1, j=1.000.000.000In those cases I would just build a list of prime numbers up to 1024, and do brute-force divisibility tests. Or better yet, when B is small but j is very large, you might try generating the B-smooth number set directly, by recursion:to generate_B_smooth(base, current_prime, results_container, limit):  current <- base.  while current < limit:    Append current to results_container.    if current_prime > 2: generate_B_smooth(current, previous_prime(current_prime), results_container, limit).    current <- current * current_prime.generate_B_smooth(1, largest_prime_under(1024), new_container(), LIMIT).;Quote:Original post by ghostrider_well the number are big enough.. the project is the following:find the B-smooth numbers between i and j, and the some testcases that it will be tested are:B=1024, i=1, j=1.000.000B=1024, i=1, j=100.000.000B=1024, i=1, j=1.000.000.000Quote:In those cases I would just build a list of prime numbers up to 1024, and do brute-force divisibility tests. Or better yet, when B is small but j is very large, you might try generating the B-smooth number set directly, by recursion:ok think i got it..so to conclude.. i am about to build a list of primes up to 1024.. then i 've got two ideas.. the one mentioned above-brute force divisibility testings..but the other one- which if it is true may be fastest is: start from the nearest prime number to sqrt(n), see if it divides the number.. if not go to the previous one.. the firs to find is the largest.. do you think its ok??my problem in the second idea is what will happen if the sqrt(n) is bigger than 1024.. how can i check if there is at least one prime factor between 1024 and sqrt(n)..??ps:alvaro i accidentally read a post of you for prime factors, 2 years ago.. you mntioned something for sqrt(n) and i took th idea from there.. can you explain it further??   ;  any idea for that: if i want to find alla the numbers between ,lets say 1 and 100.000.000 whose largest prime factor is less than 1024...??what do you mean generate the B-smmoth number??   