Re: Breaking Large Composite Numbers...???

On Dec 15, 12:16 pm, Christian Siebert <ib...@xxxxxx> wrote:
Phil Carmody wrote:
And the LA for a 1024-bit number will require a machine
with somewhere between 1 and 10 Tbytes of memory..
(my best estimate is about 3 Tbytes)
Looking atwww.top500.orgit seems that there are already hundreds of
supercomputers that have more than your 10 TiB of memory.

Not randomly addressible at O(1) cost by a single processor. That's
because those aren't computers, they are clusters. You seem to have
deliberately avoided paying attention to everything Bob's been saying
about the parallelisability of the current best factoring algorithms.
Which is foolish, Bob's almost certainly the single most expert in
the field contributing to sci.crypt. (But there may be lurkers who
are equally expert.)

Sorry, my intention was not to question Bob's expertise. I was rather
trying to provide some additional facts to the currently available
computing power. Maybe some more (but please don't treat this as a
question to your expertise, Phil!): The Top500 list uses the HPLinpack
to measure the performance of these machines, which *is* an LA
application (and some argue that it is - besides massively parallel apps
- the only one that runs on such huge systems). They nowadays solve full
systems of linear equations with several million unknown using double
precision calculations on hundred thousands of cores. This shows that
such applications can be well suited to run in parallel. I admit that I
don't know enough to judge about the possibility to parallelize the
sparse variants that Bob mentioned. However, the rare information I have
(like the announcement of the RSA-640 factorization) indicates that
those solvers are quite scalable too. So please share your thoughts and
provide more support that convinces me to believe that RSA-1024 is safe
for another couple of decades.


(1) Try plotting record-setting RSA factorizations against time. Do a
simple
extrapolation.

(2) Join/read the discussions on the MersenneForum relating to the
difficulties
people are *actually having* in getting the LA to scale.

(3) Try solving a sparse linear system with 15 million columns over GF
(2) yourself.
Get a parallel shared memory computer. (say an 8-core machine with
8Gbytes of memory).
Compare the run times for 1,2,4,8 processors. Unless your
implementation
is extraordinarily better than existing ones, you will find 8 cores to
be
SLOWER than 4 cores owing to data communication overhead). And the
difficulty
gets worse if you try (say) 16 cores in 2 computers connected by even
a multi-gigabyte/sec
interconnect.

Noone yet has gotten the LA to scale.

Communication Latency is a killer on sparse problems as compared
against DENSE
double-precision problems. In particular look at the
computation-time to communication-time ratios for sparse and dense
problems.
Now scale this system to the 500+ million column problem (give or take
a factor of
2) that will arise from kilobit RSA.

Clusters work well on double precision dense problems because the
machines
spend a lot of time computing in between data exchanges. The same is
NOT true
for the very very very sparse problems that arise from NFS/DL. The
computation/communication
granularity is totally different.
.

Relevant Pages

  • Re: Multi core
    ... It is hard to imagine how 4 cores ... So they are all eating CPU at once? ... I recently helped family and neighbors with their Vista computers that had huge Gigahertz computers with several cores and all that nonsense... ... All these are IDLE PROGRAMS - memory. ...
    (borland.public.delphi.non-technical)
  • Re: Verbose functional languages?
    ... Speaking of multiple cores: when I look at what's Intel talking about, ... Even memory allocation would create all kinds of mutual wait ... I'm less convinced about general use of semi-space moving collectors ...
    (comp.lang.functional)
  • Re: Target market for Intellasys.
    ... I was wrong about that Ambarella chip, it's average power requirements are more than I thought. ... With the 1 transistor dram, the substrate acts as a capacitor, so theoretically you get many times more memory density, good speed etc. ... I for one would be dropping in 10+DACS, extra processors, extra memory, and if available 36bit processor cores and full external SRAM memory buss mapped to one core. ... But such a scheme would allow customers to easily order a module populated with a desired amount of memory cores, and it would cost intellasys a lot less than putting memory on the processor. ...
    (comp.lang.forth)
  • Re: death of the mind.
    ... >> vision of science is the sterile state of their explanatory theories. ... engages in the behavior said to "show memory." ... > computers aren't animals and probably aren't like them in very many ways. ... And I've published inferential statistics when forced to - which was most of ...
    (sci.cognitive)
  • Re: self-extracting diskette image to hard disk? (or, IBM keeping inexpensive supercomputers awa
    ... >> also have brought in huge amounts of money, ... > I know what IBM was doing, ... >> claiming not only that memory would be many times larger than existing ... >> selling these super computers for $3000. ...
    (comp.os.os2.misc)