Re: Elementary group theory: Proof of Fermat-Maas primality-test (was: correcting *** ...)

I finished my side topics, namely constructing a primitive element
of the mulplicative group modulo a prime, after you've already used
the Fermat-Maas algorithm to prove it's really prime, making use of
the known factorization of p-1 that you got when you directly
constructed p from it. So now I'm finally back to directly
replying to what *** wrote:

From: "*** T. Winter" <***.Win...@xxxxxx>
Even the current methods take a considerably long time (minutes or
hours) to factor *each* 80-digit number. In that time I could
randomly synthesize thousands of 80-digit products, not just one.
Yes. But generating those numbers *is* much faster than factorising.
Primality proving is *much* faster than factorising.

Are you claiming that your suggested method
- generating random large odd numbers, applying Fermat's little
theorem as a preliminary filter to get rid of most composites,
then applying state-of-art method for testing primality of p
without knowing factorization of p-1,
is faster then my favorite method of
- directly synthesizing a known product for p-1, applying Fermat's
little theorem as a preliminary filter to get rid of most
composites, then testing primality p using the Fermat-Maas
algorithm?

Eh? What are you talking about? Have a look at:
<http://www.rsasecurity.com/rsalabs/node.asp?id=2879>
where information is given about the factorisation of RSA-200

Please see Paul Zimmermann's factoring page for more information.
->
<http://www.loria.fr/%7Ezimmerma/records/factor.html>
General-purpose Algorithms: the largest integer factored with a
general-purpose algorithm is RSA200 (200 digits), which was factored
on May 9, 2005 by Bahr, Boehm, Franke and Kleinjung.
That's worded poorly. In fact *much* larger numbers have been
factorized by general-purpose algorithms. For example, I bet
everyone reading this newsgroup can factor this 245-digit number
19323349832288915105454068722019581055401465761603328550184537628902466746415537000017939429786029354390082329294586119505153509101332940884098040478728639542560550133727399482778062322407372338121043399668242276591791504658985882995272436541441
by using the brute-force general-purpose factorization algorithm.

Back to the RSA page:
The sieving effort is estimated to have taken the equivalent of 55
years on a single 2.2 GHz Opteron CPU. The matrix step reportedly took
about 3 months on a cluster of 80 2.2 GHz Opterons. The sieving began
in late 2003 and the matrix step was completed in May 2005.
So somebody buys 80 high-speed computers, probably each costing
$2000, for a total investment of $160,000, and then squanders their
best years playing a factorization game for a prize of only a few
thousand dollars prize? Where's the profit in that?

All it proves is that some people with lots of money to burn are
willing to burn it in many ways including this particular one.
Personally I think Gosper has a better idea of how to burn money,
namely on fine restaurant food (Chinese or Indian), something you
can actually enjoy, or how to make more productive use of a good
computer system, namely developing new algorithms for summing
hypergeometric series. Although in my younger non-serious days I
did fall victim to the urge to answer a Martin Garder challenge:
I was the first person, on IBM 1620 computer, to count the number
of ways to bisect chessboards of size 8*8 and 9*9. Later, after I
had my own personal computer in 1977, and I wrote a DM2500 emulator
for it, which ran entirely on interrupts, having
a mainline program of just
loop: bra loop
while waiting for interrupts, I decided to make some use of those
wasted idle-loop CPU cycles, so I wrote another version of my old
chessboad-bisect counter, duplicating my old IBM 1620 results, and
then continuing by being the first (AFAIK) to count bisections of
10*10 and 11*11 boards. It's amazing how fast my own personal MOS
6502 was compared to the ancient IBM 1620! Unfortunately Martin
Garder was no longer interested in such challenge tasks.
But note that I was only using idle cycles between interrupts.
I wasn't consuming major compute power that could have been used
elsewhere.

Given that a bunch of people had money to burn in the form of
cracking the RSA 200-digit challenge, and also the RSA 576-bit and
RSA 640-bit challenges, I don't suggest the NSA use any RSA p*q
shorter than a thousand bits. In that case, you really would need
to trojan thousands or millions of computers to crack it, and you
*would* get caught before you finished the task.

So either you use a reasonable number of computers somebody can
actually afford to crack a toy challenge, costing more money for
the computers than you get in the prize, or you hihack millions of
PCs to crack something more profitable, and go to prison, or you
just directly hijack computers of interest, and steal credit-card
data and use it to steal millions of dollars, or send out billions
of spam per day, and you don't get caught because victims of spam
and credit-card theft are helpless, and the government just doesn't
care.
.

Loading