Need a paper!

[xilman]

Originally Posted by Citrix

Paul,

Thank you for your reply. I do not know any mathematicians, so I guess people on this forum will have to read my paper first.

Any way, what does relevant mean? When will a citation be relevant?

Suppose you discover a new method to factor numbers, do you have to provide a history of the subject, explain all the algorithms etc? Even if your algorithm has nothing to do with any of the other algorithms other than that they have the same purpose of factoring numbers?

Citrix

You know several of mathematicians, or people who have written mathematical papers --- which is not the same thing at all. I'm not saying that all of them, or even any of them, will be suitable but you won't find out unless you try.

Here is a short and incomplete list to get you started.

• Me
• Bob Silverman
• Alex Kruppa
• Ernst Mayer

You will probably find more with the aid of a search engine, which is something I suggested you should use in an earlier post. Here is one which you may find useful: http://www.ams.org/mathscinet/ though, to be fair, the full site is not available to those (like me) do not have a paid-for subscription.

Relevance: no, a complete history of factoring would not be relevant to the discovery of a new factoring algorithm. A one or two para introduction would be, but you would cite only one reference and that to a general text such as, perhaps, Riesel.

On the other hand, hardly ever is a new algorithm completely new, with no similarities to previously known algorithms. You would refer to the similar ones.


Paul

[xilman]

Originally Posted by Citrix

I will get some thing ready over the winter break.
Though there is not much to discuss, because the algorithm works, I implemented and tested it. The presentation of the paper, is I would like to focus on, since most of my math knowledge is from the internet.

Citrix

Ok, here's your first bit of feedback.

Does your algorithm always work? Have you proved this? Are there special cases for which it doesn't work?

How fast does your algorithm run? By this, I mean how does it scale? Does a problem N times the size take log(N) times as long? N times? N^2 times? 2^N times? Have you proved this?

Is your algorithmic probablistic? If so, what is the expected run time? What is the maximum run time?

Lots of other things for you to think about.


Paul

[akruppa]

Some things I'd like to read about in a paper:

Does the algorithm borrow ideas from earlier algorithms? If so, which ones?
Which parts are new? Why did you do it like that?
How does the new algorithm compare to existing ones? Run time, memory requirements? Do the improvements work for all cases, or only special ones?
Which problems remain with the new algorithm, i.e. what could be further improved? Are these problems well known open problems that were encountered in related algorithms?

And giving a brief overview of existing literature in the introduction section of the paper will show to the reviewer/reader that you did the necessary background reading on the subject which helps you paper being taken seriously.

Alex

[ewmayer]

I would suggest that before even beginning to write a manuscript, the following should be addressed satisfactorily, in the order given:

1) Correctness - does the algorithm work for all cases? If not, what are the exceptional cases?

2) Novelty - assuming (1) is satisfied, i.e. the algorithm works in all cases or all but a small (and well-defined) subset of exceptional cases, is the algorithm genuinely new? If there is overlap or similarity with known algorithms (which is nearly inevitable), then to what degree?

3) Assuming the algorithm is both correct and sufficiently novel, what is the asymptotic runtime, as a function of both input and penultimate-factor size? This is the same as asking, "is the algorithm useful?" If there is an asymptotic difference between the current-best implementation and what is achievable using known fast-arithmetic algorithms (e.g. fast multiply and mod), indicate both work estimates.

Unless the algorithm is correct, sufficiently novel and useful (or likely to be, with a reasonable level of software optimization), I doubt you will have a chance to get it published in any respectable venue.

[fatphil]

Originally Posted by Citrix

Since the algorithm is not related to any methods that exists in journals so far, I am not sure if I should cite anything or not?

How do you choose what to cite?

Begin with a very short summary and taxonomy of previously known techniques. You can probably summarise discrete logs in a 2 paragraphs. If you're Dan Bernstein, that is.

[xilman]

Originally Posted by fatphil

Begin with a very short summary and taxonomy of previously known techniques. You can probably summarise discrete logs in a 2 paragraphs. If you're Dan Bernstein, that is.

If you are DJB, your bibliography for an otherwise straightforward paper will probably run to over 200 references.

Dan is a bright guy, but I really dislike his habit of including a reference to almost every paper from the last half-century which may conceivably have any point of contact with his.


Paul

[fatphil]

Originally Posted by xilman

If you are DJB, your bibliography for an otherwise straightforward paper will probably run to over 200 references.

Dan is a bright guy, but I really dislike his habit of including a reference to almost every paper from the last half-century which may conceivably have any point of contact with his.

He sometimes assumes the dual role of both research mathematician and archivist/historian, and the overlap does cause the effect you see. Often, one of the references will be something along the lines of "as summarised in [93]", and almost every other reference (20 of them, say) in the paragraph can be ignored!

Personally I just love his historian role. He's always happy to point out that other people really had gaping holes in their background knowledge! In the most blunt of ways. (I'm thinking of the FFT one, for example, where he even slashes at Knuth.)

[Numbers]

Being one of the great un-washed who have never heard of D J Bernstein, I did a Google search for him and found his home page where, by one of those strange coincidences that sometimes make life seem more interesting than it really is, he includes some advice on writing good Maths papers. He also includes a number of links to other sources (not all of which are actually published on the web) of similar advice. Given the original purpose of this thread I thought Citrix at least might be interested.

Notes on writing papers:
http://cr.yp.to/writing.html

The devil’s guide to citing the literature:
http://cr.yp.to/bib/devil-cite.html

[Citrix]

Thanks numbers, I will try to read the site.

By the way who is D J Bernstein? I have never heard of him? What field of math does he work in?

Citrix

[Numbers]

Originally Posted by Citrix

Thanks numbers, I will try to read the site.
By the way who is D J Bernstein? I have never heard of him? What field of math does he work in?

Is it just me, or does anyone else find this funny?

[akruppa]

Originally Posted by Numbers

Is it just me, or does anyone else find this funny?