[QUOTE=R.D. Silverman;262990]Having an objective of finding just one small factor
of a number that is too large to be fully factored is a pointless
waste of time if the objective is JUST that small factor.[/QUOTE]

I'd say that's a matter of opinion. :smile: Some might see it a waste of time to fully factor any number, or to do a GIMPS-style search for prime numbers. You see it as a waste of time to find a small factor of a number that you probably won't be fully factoring. Doesn't mean anyone's necessarily right or wrong, just different opinions.

[QUOTE=Mini-Geek;262994]I'd say that's a matter of opinion. :smile:
[/QUOTE]

Agreed. But not all opinions are created equal. :smile:

I suggest that you take a poll among mathematicians
who work in this domain...Finding a small factor is useful if one
is eliminating primality candidates. But it is not very helpful in
solving other problems. My opinion about the OPN search is known.
But finding one small factor isn't very helpful even there, whereas
full factorizations are.

Over time as one gains experience and mathematical maturity, one
gets a feel for what is important. Think of it as wine-tasting.
The opinion of people with experience, as opposed to dilletantes makes
a difference.

For Cunningham numbers (those with prime base) full factorizations are
useful because they reveal the structure of finite fields. Knowing said
structure has uses in other parts of mathematics, even practical ones
such as constructing good pseudo-rngs.

[QUOTE=R.D. Silverman;262980]Unfactored 2^n-1 for n < 2000 has only 4 exponents??

Clearly you count differently from the way everyone else does.[/QUOTE]
That can be rephrased to say "there are 4 'genuine composites'", i.e. composite numbers for which we do not know any prime factor.

[QUOTE=alpertron;263360]That can be rephrased to say "there are 4 'genuine composites'", i.e. composite numbers for which we do not know any prime factor.[/QUOTE]

You can't mean what you wrote here. I expect that most of the
factorizations of 2^n-1 for n < 2000 are incomplete; these incomplete
factorizations [i]all[/i] leave composite cofactors for which we do not know
any prime factor.........

I have never seen the term "genuine composite" in a book or paper.
Can you give a reference???

[QUOTE=R.D. Silverman;263394]You can't mean what you wrote here. I expect that most of the
factorizations of 2^n-1 for n < 2000 are incomplete; these incomplete
factorizations [i]all[/i] leave composite cofactors for which we do not know
any prime factor.........

I have never seen the term "genuine composite" in a book or paper.
Can you give a reference???[/QUOTE]
I've read that in "Prime Numbers" by Richard Crandall and Carl Pomerance. The four numbers are: 2[SUP]1061[/SUP]-1, 2[SUP]1277[/SUP]-1, 2[SUP]1619[/SUP]-1 and 2[SUP]1753[/SUP]-1. The cofactors you said above are not Mersenne numbers themselves so those do not count.

[QUOTE=alpertron;263396]I've read that in "Prime Numbers" by Richard Crandall and Carl Pomerance.[/QUOTE]
Do they give any reasoning for their use of the term? I think they got it backwards; if any composites deserve to be called "genuine", it should be those with known factors, because we can quite concretely write them as products of other numbers, thereby proving without doubt that they are indeed composites. In contrast, a composite with no known factors is only known to be composite because some primality test reported it as composite, and it may be very difficult to verify the result.

[QUOTE=Random Poster;263455]In contrast, a composite with no known factors is only known to be composite because some primality test reported it as composite, and it may be very difficult to verify the result.[/QUOTE]Proof of compositeness is easy and fast. Verification is simple even without knowing any factors.

[QUOTE=retina;263456][QUOTE=Random Poster;263455][QUOTE=alpertron;263396]I've read that in "Prime Numbers" by Richard Crandall and Carl Pomerance. The four numbers are: 2[SUP]1061[/SUP]-1, 2[SUP]1277[/SUP]-1, 2[SUP]1619[/SUP]-1 and 2[SUP]1753[/SUP]-1. The cofactors you said above are not Mersenne numbers themselves so those do not count.[/QUOTE]
Do they give any reasoning for their use of the term? I think they got it backwards; if any composites deserve to be called "genuine", it should be those with known factors, because we can quite concretely write them as products of other numbers, thereby proving without doubt that they are indeed composites. In contrast, a composite with no known factors is only known to be composite because some primality test reported it as composite, and it may be very difficult to verify the result.[/QUOTE]
Proof of compositeness is easy and fast. Verification is simple even without knowing any factors.[/QUOTE]

Really? The notion of genuine composites is discussed in PN:ACP in the section on Fermat numbers (§1.3.2, at least in the first edition), and it specifically references F[sub]14[/sub], F[sub]20[/sub], F[sub]22[/sub] and F[sub]24[/sub]. Of course, two of those have since had a factor found.

Shall we ask ewmayer and jasonp whether their proof of F[sub]24[/sub]'s compositeness was easy and fast? And even today, over a decade later, can you perform a "simple" verification of this fact? Will your verification be substantially simpler than the original proof?

(Speaking of which, Ernst and Jason: is the full F[sub]24[/sub] Pépin residue generated by your proof available anywhere? I know the Selfridge-Hurwitz residues are in the paper, but the full residue would be nice to have, just for, uh, fun or something.)

@Random: I'm not sure of the justification for choosing the term genuine to describe such a composite. Perhaps a better word didn't suggest itself. Would you care to put forward an alternative? In any case, the authors talk a bit (in exercise 1.79) about some interesting aspects of this notion of "genuineness". Specifically, given any composite C with no known factors, it follows immediately that 2[sup]C[/sup]-1 is also composite, and chances are good that no factors of [I]it[/I] are known either. So there can't really be any largest genuine composite.

I may have the F24 residue on a backed-up old hard drive. You can make up random garbage and it should work just as well :)

[QUOTE=jyb;263484]Shall we ask ewmayer and jasonp whether their proof of F[sub]24[/sub]'s compositeness was easy and fast?[/QUOTE]It was easier and faster than factoring it. :wink:

[QUOTE=jasonp;263491]I may have the F24 residue on a backed-up old hard drive. You can make up random garbage and it should work just as well :)[/QUOTE]

Not really, depending on what one wants to do. If a factor of F[sub]24[/sub] is found, then the full Pépin residue would be needed to use the Suyama method for proving the cofactor composite (which would be a lot faster than a corresponding Fermat test). In fact, the abstract of your paper says:

[QUOTE]We deposited a final Pépin residue for possible use by future investigators in the event that a proper factor of F[sub]24[/sub] should be discovered.[/QUOTE]

So it would seem that there's a residue bank somewhere and you guys made a deposit. If I want to show that my F[sub]24[/sub] cofactor is composite with minimal fuss, I'll need to make a withdrawal. Please can you direct me to the teller window?*

*I don't actually have a cofactor to test, so this is all academic. I'm just wondering where one might obtain the residue.