mersenneforum.org Smooth?
 Register FAQ Search Today's Posts Mark Forums Read

 2004-10-31, 03:03 #1 Xyzzy     "Mike" Aug 2002 23·3·331 Posts Smooth? In several threads I have come across a term that I do not understand: "smooth group order" What does this mean? Not only do I not know what "smooth" means, I have no idea what a "group order" is... Thanks!
2004-10-31, 08:03   #2
Chris Card

Aug 2004

2·5·13 Posts

Quote:
 Originally Posted by Xyzzy In several threads I have come across a term that I do not understand: "smooth group order" What does this mean? Not only do I not know what "smooth" means, I have no idea what a "group order" is... Thanks!
An integer is said to be "smooth" if all its prime factors are smaller than a given bound (the bound usually being clear from the context).

A group is an abstract mathematical object consisting of a set and an operation that produces a member of the set from pairs of members of the set, and which satisfies 4 axioms (I won't give all the details here). The set could be finite or infinite, but in the case that it is finite, then the number of elements in the set is called the "order" of the group, or the "group order". A simple example of a group is the set of integers {1, ..., p-1}, p a prime number, with the operation being multiplication modulo p, and in this case the group order is p-1.

So, "smooth group order" refers to a finite group whose order is smooth. One place this comes up is in the P-1 factorisation method, where the success of the method depends on the group in the example described above having smooth group order.

HTH

Chris

2004-10-31, 08:07   #3
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

33·389 Posts

Quote:
 Originally Posted by Xyzzy In several threads I have come across a term that I do not understand: "smooth group order" What does this mean? Not only do I not know what "smooth" means, I have no idea what a "group order" is... Thanks!
I assume you know what a group is, in mathematical jargon. If not, say so and I'll explain.

The order of a group is the number of elements in it. It's just an integer

The term "smooth" when applied to an integer means that the integer may be factored entirely into small primes. This, of course, begs the question of what is meant by "small". Frequently it can be deduced from context. Where greater precision is needed, the term "B-smooth" is generally used. A B-smooth integer has all its prime factors less than or equal to B. So, for example, 128 is 5-smooth (indeed, it's 2-smooth), as are 125 and 120, but 121 is not 5-smooth, though it is 11-smooth.

Paul

 2004-10-31, 14:33 #4 Xyzzy     "Mike" Aug 2002 23×3×331 Posts Many thanks! I actually took "finite mathematics" which dealt mostly with groups, sets and stuff like that, but I totally forgot about it! So if I understand right, "smooth" works like this: 128 = 2Γ2Γ2Γ2Γ2Γ2Γ2 <- 2 smooth 125 = 5Γ5Γ5 <- 5 smooth 120 = 2Γ2Γ2Γ3Γ5 <- 5 smooth 121 = 11Γ11 <- 11 smooth Is it safe to say that you must have the absolute factorization before you can assign a "smooth" value? I'm not too sure where the "b" is coming from when you mention "b-smooth"... Finally, what is the correct way to write out a factorization? I've seen it done several ways but I imagine there is an accepted proper way...
2004-11-04, 16:21   #5

"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts

Quote:
 Originally Posted by Xyzzy Is it safe to say that you must have the absolute factorization before you can assign a "smooth" value?
You just have to know the largest prime factor.

Quote:
 I'm not too sure where the "b" is coming from when you mention "b-smooth"...
Bounds -- "b-smooth" would often be used in the context of discussing a factorization method such as P-1 that had one or more bounds as parameters.

Quote:
 Finally, what is the correct way to write out a factorization? I've seen it done several ways but I imagine there is an accepted proper way...
There's no one proper way -- it depends on the context. IMO writing out the multiplication as in "120 = 2Γ2Γ2Γ3Γ5" could be considered a fairly standard way to communicate the factor list. Since commas take less space than x-es, one could see "2,2,2,3,5", "((2,3),(3,1),(5,1))" and "(3,1,1)" whenever the context directed that multiplication or exponentiation be used in the appropriate combination.

 2004-11-04, 18:20 #6 jocelynl   Sep 2002 2×131 Posts Many Mersenne numbers have a factor that is M-smooth since M is the largest factor of p-1 ex: 2^29-1 has factor 233 = 2.2.2.29+1 Joss Last fiddled with by jocelynl on 2004-11-04 at 18:24

 Similar Threads Thread Thread Starter Forum Replies Last Post XYYXF Computer Science & Computational Number Theory 0 2014-12-05 17:32 Sam Kennedy Factoring 5 2012-11-10 07:54 flouran Math 12 2009-12-25 16:41 Yamato Math 1 2005-12-11 11:09 bonju Factoring 9 2005-08-26 13:29

All times are UTC. The time now is 17:38.

Wed Jan 20 17:38:16 UTC 2021 up 48 days, 13:49, 0 users, load averages: 2.65, 3.48, 3.63