mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2004-10-31, 03:03   #1
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

175408 Posts
Default 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!
Xyzzy is offline   Reply With Quote
Old 2004-10-31, 08:03   #2
Chris Card
 
Chris Card's Avatar
 
Aug 2004

2×5×13 Posts
Default

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
Chris Card is offline   Reply With Quote
Old 2004-10-31, 08:07   #3
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

29·367 Posts
Default

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
xilman is online now   Reply With Quote
Old 2004-10-31, 14:33   #4
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

803210 Posts
Default

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...
Xyzzy is offline   Reply With Quote
Old 2004-11-04, 16:21   #5
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

1E0C16 Posts
Default

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.
cheesehead is offline   Reply With Quote
Old 2004-11-04, 18:20   #6
jocelynl
 
Sep 2002

10616 Posts
Default

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
jocelynl is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Consecutive p-smooth integers XYYXF Computer Science & Computational Number Theory 0 2014-12-05 17:32
Not smooth enough numbers Sam Kennedy Factoring 5 2012-11-10 07:54
Distribution of Smooth Numbers flouran Math 12 2009-12-25 16:41
Smooth Numbers Yamato Math 1 2005-12-11 11:09
NFS and smooth norm MOD N ? bonju Factoring 9 2005-08-26 13:29

All times are UTC. The time now is 19:10.

Tue Apr 13 19:10:09 UTC 2021 up 5 days, 13:51, 1 user, load averages: 2.76, 4.00, 4.62

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.