740:'Here's what I know, or seem to remember. I introduced the 1-parameter L notation in my paper "Analysis and comparison of some integer factoring algorithms" but not exactly in the way you write it. Instead of L_n, I wrote it as L^a, where the variable "n" was understood from context. I used the letter "L" only because there were various logs involved. I had been in the habit of labeling more complicated expressions with either an upper case or lower case "L" in earlier papers (for example see p.184 of my paper "On the distribution of amicable numbers, II", which is from 1981 and is #30 on my website)." '
634:. See Section 2. I don't know if Pomerance was the first to use it or not, but he definitely resolved the discrepancies among different analyses of factoring algorithms in the number theory literature in this paper. This is a classic paper. It has been cited 173 times according to Google scholar. I'm also pretty confident that the two parameter version came into being from the Number Field Sieve. Prior to that they were only using the one parameter version because the functions they were interested in always had
693:. So if nobody opposes, I would like to edit this article to cite this, and to remove the big O which only seems to be used by Handbook of Applied Cryptography (HAC) and sources that cite it. The standard definition does not involve any big O. BTW, I'm still chasing the history of the one parameter version, but Arjen told me the thinks Pomerance might have invented it in the Analysis and comparison of some integer factoring algorithms paper that I cited above. I hope to be to the bottom of this by tomorrow.
84:
74:
53:
22:
668:. I've looked through the earliest two papers on the number field sieve ("The Factorization of the Ninth Fermat Number" and "The Number Field Sieve" by Lenstra Lenstra Manasse Pollard) and neither use the two parameter L-notation. I don't have my "The Development of the Number Field Sieve" book in front of me now, but I expect that it might have been first introduced there.
880:
Note that despite the two parameters, L notation is less general than big-O and little-o notation, although more "precise", since it bounds the function asymptotically from both sides. It simply does not cover functions that grow faster than polynomial with n. To cover exponential growth, I guess one
876:
The following may be unfamiliar/nonobvious to some readers: ln(n) may represent the length of representation of a number n. When stating that "AKS is has polynomial complexity", it is implicitly understood to refer to a polynomial in ln(n), where n is the number to be tested. Otherwise, even naïve
586:
running time and not to an upper bound, thus the Big O outside is inappropriate. I have not been able to find sources other than the HAC that use a Big O in their definition of L. What is needed now are suitable (original?) references for inclusion in the article, which define L without the Big O,
485:
I remark that the use of the big O here is non-standard and is meaningless. The little o in the exponent takes care of everything: adding a big O on the outside has no effect. This seems to be a mistake in the
Handbook of Applied Cryptography (HAC) which has not yet been reported to the authors,
757:
Note that if you add a history section be careful that the information can be referenced. You may certainly tell that the one-parameter version was first found in a paper by C. Pomerance, and that it got subsequently adapted later by other authors, ultimately leading to the current two-parameter
629:
For the one parameter version, I would suggest using reference: Carl
Pomerance, Analysis and comparison of some integer factoring algorithms, Computational Methods in Number Theory, Part I, H.W. Lenstra, Jr. and R. Tijdeman, eds., Math. Centre Tract 154, Amsterdam, 1982, 89-139. It can be
688:
Folks, I have the answer (thanks to Arjen
Lenstra). The two parameter version was introduced by Arjen and Hendrik Lenstra in their "Algorithms in Number Theory" article. They introduced it to analyze a Coppersmith Discrete Log algorithm. See section 3.16 of
861:
Since L has to parameters, the article should discuss their respective impacts and in the same vein perhaps provide some rules of thumb on how minimization of each should be prioritized for the sake of science or of communication. (If that makes sense.)
759:
606:
552:
on this topic. The published number theory papers that use it are the primary source. What published number theory papers use thie big O? I'm pretty sure
Pomerance, H. Lenstra, and A. Lenstra never have a big O in any of their papers that use it.
458:
587:
both for the one and the two parameter version. Note that for the examples given on this article it does not matter whether they are given with or without the Big O (and in fact the GNFS would be more appropriately described without it).
389:
832:
I struggled understanding this until I realized that the o(1) added to c represents any function whose limit is 0 as n approaches infinity. This follows from the limit definition of small-o:
140:
486:
but anyone who looks through the actual published scientific papers that use the notation will see that none use big O. I have been discussing this with user Nageh on his talk page. See
234:
192:
438:
666:
857:
since ln(d)/( ln(n)^alpha ln(ln(n))^( 1-alpha ) ) approaches 0 as n approaches infinity, it can simply be absorbed by the o(1), so that d * L(alpha, c) = L(alpha, c)
807:
440:
expands to in big-O seems to have something to do with the distribution of prime numbers . The algorithms measured by L-notation involve small prime numbers (for
758:
version. Anyway, a few words about historical introduction of the notation would certainly be interesting. We may also add a
Properties section according to
448:
and what-not), so L-notation might be a good way to filter out the statistical variation for similarly-sized inputs , which big-O is too fine-grained for.
928:
130:
923:
602:
454:
884:
L_e(alpha, beta, gamma, c) = exp( ( c + o(1) ) n^(alpha/(alpha+beta+gamma)) ln(n)^(beta/(alpha+beta+gamma)) ln(ln(n))^(gamma/(alpha+beta+gamma)) )
162:
In the main part of the article, we say α=1 gives a "fully exponential" function. However, in the example, α is 1, yet we say the function is
106:
897:
Given the "notation abuse" issues with big-O (equality vs. set membership etc.), a clearer instruction on how to use L notation is warranted.
900:
I am just scraping the surface of this topic, so I hope someone with the expertise will find my feedback useful for improving the article.
548:
EmilJ, that's a valid point. But it is still not the standard definition. Handbook of
Applied Cryptography should not be considered the
814:
569:
248:
97:
58:
877:
trial division by all integers smaller than n has "polynomial complexity" in n (i.e. at most O(n^3) or so, if division is O(n^2)).
737:
Folks, I got to the bottom of the 1-parameter version and why the letter "L" was chosen. I emailed Carl
Pomerance and he replied:
582:
I'm reposting my conclusion here. The complexity of the GNFS and other similar sub-exponential algorithms refers to the
33:
329:
467:
609:
could indeed be a suitable link to be used here to rewrite the definition (the section is written
Lenstra himself).
21:
818:
748:
698:
673:
565:
495:
244:
504:
Adding a big O on the outside has the effect of making it only an upper bound. For example, the function
39:
83:
854:= exp( ( c + o(1) + ln(d)/( ln(n)^alpha ln(ln(n))^( 1-alpha ) ) ) ln(n)^alpha ln(ln(n))^( 1-alpha ) )
789:
L-notation is used for growth between polynomial and exponential growth with respect to the length of
320:. For example, a bit of follow-the-footnotes suggests that H. Lenstra may have invented the notation:
690:
557:
475:
310:
207:
165:
631:
105:
on
Knowledge. If you would like to participate, please visit the project page, where you can join
744:
694:
669:
561:
491:
408:
89:
901:
637:
73:
52:
845:
A relevant example of what this means is what happens when multiplying by a constant factor d:
287:
239:
445:
264:
We currently have a basic definition, plus a rather unhelpful example. Can anyone provide:
905:
766:
720:
614:
592:
540:
487:
471:
317:
194:. If these statements are both right (which I doubt), they are certainly confusing. --
549:
272:
792:
917:
314:
306:
283:
195:
441:
102:
762:
716:
610:
588:
537:
462:
79:
840:
When, as in the present case, g(x) = 1, f is o(g)=o(1) requires lim_{x--: -->
848:
d * L(alpha, c) = d * exp( ( c + o(1) ) ln(n)^alpha ln(ln(n))^( 1-alpha ) )
323:"At this point we need an unproved conjecture. For a real number χ : -->
893:
But this would still not cover fast-growing functions like n! and n^n.
785:
Too confusing to me until I reached the, "When alpha is 0..." So here:
887:
or, sacrificing the exp( ( c + o(1) ) ln(ln(n))^gamma ) part, just:
457:
entry on "L-notation", pp.358, could be a useful source in general
909:
822:
770:
752:
724:
702:
691:
https://openaccess.leidenuniv.nl/bitstream/1887/3825/1/346_085.pdf
677:
618:
596:
573:
543:
499:
478:
291:
253:
198:
394:- H. W. Lenstra, Jr., "Factoring integers with elliptic curves",
851:= exp( ln(d) + ( c + o(1) ) ln(n)^alpha ln(ln(n))^( 1-alpha ) )
632:
http://www.math.dartmouth.edu/~carlp/PDF/analysiscomparison.pdf
890:
L_e(alpha, c) = exp( ( c + o(1) ) n^alpha ln(n)^( 1-alpha ) )
15:
869:
L(0, c) = exp( ( c + o(1) ) ln(ln(n)) ) = ln(n)^( c + o(1) )
236:
is exponential in ln n although it's just polynomial in n.
268:
History: who introduced this notation? Who uses it now?
301:
is named for (and possibly also by) some person named
866:
L(1, c) = exp( ( c + o(1) ) ln(n) ) = n^( c + o(1) )
795:
640:
411:
332:
210:
168:
101:, a collaborative effort to improve the coverage of
801:
660:
432:
384:{\displaystyle L(x)=e^{\sqrt {\log x\log \log x}}}
383:
228:
186:
520:. The latter only contains functions of the form
271:Significance: why/when is this used instead of
8:
781:Would this be accurate for the introduction?
305:. Topping the list would be candidates like
715:Go ahead! Thanks for finding all this out!
19:
872:L(alpha, c) interpolates between the two.
488:User_talk:Nageh#General_Number_Field_Sieve
47:
794:
650:
639:
603:Encyclopedia of Cryptography and Security
455:Encyclopedia of Cryptography and Security
410:
352:
331:
215:
209:
173:
167:
49:
743:We should add a history sub-section.
278:An example where α is not zero or one?
260:More info needed so this is not a stub
7:
405:The peculiar mouthful that a simple
95:This article is within the scope of
38:It is of interest to the following
835:f is o(g) means that lim_{x--: -->
297:Tentatively, I would say that the
14:
929:Low-priority mathematics articles
115:Knowledge:WikiProject Mathematics
924:Start-Class mathematics articles
229:{\displaystyle n^{\frac {1}{2}}}
187:{\displaystyle n^{\frac {1}{2}}}
118:Template:WikiProject Mathematics
82:
72:
51:
20:
135:This article has been rated as
427:
415:
342:
336:
1:
881:could define something like:
479:17:51, 27 December 2008 (UTC)
292:14:58, 27 December 2008 (UTC)
109:and see a list of open tasks.
910:10:03, 13 January 2023 (UTC)
433:{\displaystyle L(\alpha ,c)}
254:19:52, 18 October 2007 (UTC)
771:10:02, 13 August 2010 (UTC)
753:21:46, 12 August 2010 (UTC)
725:07:30, 12 August 2010 (UTC)
703:07:17, 12 August 2010 (UTC)
678:23:41, 11 August 2010 (UTC)
661:{\displaystyle \alpha =1/2}
619:07:59, 11 August 2010 (UTC)
597:07:55, 11 August 2010 (UTC)
574:20:57, 10 August 2010 (UTC)
544:13:04, 10 August 2010 (UTC)
500:12:46, 10 August 2010 (UTC)
199:16:05, 30 August 2007 (UTC)
945:
823:08:44, 6 April 2014 (UTC)
134:
67:
46:
516:), whereas it is not in
141:project's priority scale
398:vol. 126 pp. 670, 1987.
98:WikiProject Mathematics
803:
662:
630:downloaded from here:
532:) converges to 1/2 as
434:
385:
230:
204:The article's right.
188:
28:This article is rated
804:
663:
435:
396:Annals of Mathematics
386:
231:
189:
828:Clarification needed
793:
638:
601:Jafet's link to the
409:
330:
208:
166:
121:mathematics articles
836:inf} f(x)/g(x) = 0
799:
658:
536:goes to infinity.—
430:
381:
226:
184:
90:Mathematics portal
34:content assessment
802:{\displaystyle n}
577:
560:comment added by
378:
252:
223:
181:
155:
154:
151:
150:
147:
146:
936:
808:
806:
805:
800:
667:
665:
664:
659:
654:
576:
554:
439:
437:
436:
431:
390:
388:
387:
382:
380:
379:
353:
242:
235:
233:
232:
227:
225:
224:
216:
193:
191:
190:
185:
183:
182:
174:
123:
122:
119:
116:
113:
92:
87:
86:
76:
69:
68:
63:
55:
48:
31:
25:
24:
16:
944:
943:
939:
938:
937:
935:
934:
933:
914:
913:
841:inf} f(x) = 0.
830:
791:
790:
783:
636:
635:
555:
407:
406:
348:
328:
327:
262:
211:
206:
205:
169:
164:
163:
160:
158:Flawed example?
120:
117:
114:
111:
110:
88:
81:
61:
32:on Knowledge's
29:
12:
11:
5:
942:
940:
932:
931:
926:
916:
915:
896:
875:
865:
860:
844:
839:
829:
826:
811:
810:
798:
782:
779:
778:
777:
776:
775:
774:
773:
741:
738:
732:
731:
730:
729:
728:
727:
708:
707:
706:
705:
683:
682:
681:
680:
657:
653:
649:
646:
643:
624:
623:
622:
621:
599:
580:
579:
578:
550:primary source
482:
481:
450:
449:
429:
426:
423:
420:
417:
414:
403:
402:
401:
400:
399:
392:
377:
374:
371:
368:
365:
362:
359:
356:
351:
347:
344:
341:
338:
335:
280:
279:
276:
273:big O notation
269:
261:
258:
257:
256:
237:
222:
219:
214:
180:
177:
172:
159:
156:
153:
152:
149:
148:
145:
144:
133:
127:
126:
124:
107:the discussion
94:
93:
77:
65:
64:
56:
44:
43:
37:
26:
13:
10:
9:
6:
4:
3:
2:
941:
930:
927:
925:
922:
921:
919:
912:
911:
907:
903:
898:
894:
891:
888:
885:
882:
878:
873:
870:
867:
863:
858:
855:
852:
849:
846:
842:
837:
833:
827:
825:
824:
820:
816:
815:72.226.86.106
796:
788:
787:
786:
780:
772:
768:
764:
760:
756:
755:
754:
750:
746:
745:Scott contini
742:
739:
736:
735:
734:
733:
726:
722:
718:
714:
713:
712:
711:
710:
709:
704:
700:
696:
695:Scott contini
692:
687:
686:
685:
684:
679:
675:
671:
670:Scott contini
655:
651:
647:
644:
641:
633:
628:
627:
626:
625:
620:
616:
612:
608:
604:
600:
598:
594:
590:
585:
581:
575:
571:
567:
563:
562:Scott contini
559:
551:
547:
546:
545:
542:
539:
535:
531:
527:
523:
519:
515:
511:
507:
503:
502:
501:
497:
493:
492:Scott contini
489:
484:
483:
480:
477:
473:
469:
465:
464:
459:
456:
452:
451:
447:
443:
424:
421:
418:
412:
404:
397:
393:
375:
372:
369:
366:
363:
360:
357:
354:
349:
345:
339:
333:
326:
325:
322:
321:
319:
316:
312:
308:
304:
300:
296:
295:
294:
293:
289:
285:
277:
274:
270:
267:
266:
265:
259:
255:
250:
246:
241:
238:
220:
217:
212:
203:
202:
201:
200:
197:
178:
175:
170:
157:
142:
138:
132:
129:
128:
125:
108:
104:
100:
99:
91:
85:
80:
78:
75:
71:
70:
66:
60:
57:
54:
50:
45:
41:
35:
27:
23:
18:
17:
899:
895:
892:
889:
886:
883:
879:
874:
871:
868:
864:
859:
856:
853:
850:
847:
843:
838:
834:
831:
812:
784:
583:
533:
529:
525:
521:
517:
513:
509:
505:
461:
446:group orders
442:factor bases
395:
302:
298:
281:
263:
240:CRGreathouse
161:
137:Low-priority
136:
96:
62:Low‑priority
40:WikiProjects
556:—Preceding
282:Thanks. --
112:Mathematics
103:mathematics
59:Mathematics
30:Start-class
918:Categories
607:L-notation
324:e, define
605:entry on
584:expected
570:contribs
558:unsigned
284:Doradus
196:Doradus
139:on the
524:where
508:is in
311:Lehmer
307:Landau
36:scale.
902:Elias
763:Nageh
717:Nageh
611:Nageh
589:Nageh
476:watch
463:Jafet
906:talk
819:talk
767:talk
749:talk
721:talk
699:talk
674:talk
615:talk
593:talk
566:talk
538:Emil
496:talk
472:play
468:work
460:. ~
453:The
444:and
318:stra
313:and
288:talk
490:.
370:log
364:log
355:log
315:Len
131:Low
920::
908:)
821:)
813:--
769:)
761:.
751:)
723:)
701:)
676:)
642:α
617:)
595:)
572:)
568:•
541:J.
498:)
419:α
373:
367:
358:
309:,
290:)
247:|
904:(
817:(
809:.
797:n
765:(
747:(
719:(
697:(
672:(
656:2
652:/
648:1
645:=
613:(
591:(
564:(
534:n
530:n
528:(
526:f
522:n
518:n
514:n
512:(
510:O
506:n
494:(
474:•
470:•
466:•
428:)
425:c
422:,
416:(
413:L
391:"
376:x
361:x
350:e
346:=
343:)
340:x
337:(
334:L
303:L
299:L
286:(
275:?
251:)
249:c
245:t
243:(
221:2
218:1
213:n
179:2
176:1
171:n
143:.
42::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
