Smooth?

[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!

[Chris Card]

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

[xilman]

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

[Xyzzy]

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...

[cheesehead]

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.

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.

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.

[jocelynl]

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