1667:
1315:). For example, if an attack succeeds in violating a security condition only with negligible probability, and the attack is repeated a polynomial number of times, the success probability of the overall attack still remains negligible.
291:
414:
2438:
2505:
751:
194:
64:
1378:
622:
155:
1580:
1467:
911:
2297:
1145:
1043:
2197:
1075:
1926:
1537:
1170:
1808:
861:
2376:
552:
1632:
1428:
1982:
1105:
942:
801:
627:
This classic definition of continuity can be transformed into the definition of negligibility in a few steps by changing parameters used in the definition. First, in the case
477:
1861:
828:
1731:
2125:
658:
2531:
2058:
1322:
functions bounding the adversary's success probability and to choose the security parameter large enough that this probability is smaller than some threshold, say 2.
503:
365:
700:
2323:
2223:
1757:
977:
451:
2032:
1003:
2589:
2002:
1652:
1487:
1298:
1278:
1258:
1235:
1215:
1195:
775:
1300:
can be any predetermined system metric and corresponding mathematical analysis would illustrate some hidden analytical behaviors of the system.
227:
2697:
2675:
2645:
2613:
2565:
1304:
1331:
381:
2739:
2389:
2444:
720:
163:
33:
2744:
1341:
557:
98:
1549:
1436:
867:
2229:
1110:
1008:
2131:
321:'s time (1680s), they were not well-defined until the late 1810s. The first reasonably rigorous definition of
1081:. This leads to the definitions of negligible functions given at the top of this article. Since the constants
1048:
2685:
1868:
1492:
1307:
is defined as polynomial running time: it has mathematical closure properties that make it tractable in the
1147:
with a constant polynomial, this shows that infinitesimal functions are a superset of negligible functions.
1764:
833:
2716:
2655:
2329:
508:
28:
2536:
2526:
1585:
1383:
334:
326:
1933:
1084:
921:
780:
456:
1815:
806:
1700:
2072:
2721:
1308:
630:
373:
306:
201:
2037:
482:
348:
2583:
663:
2667:
2693:
2671:
2641:
2637:
2628:
2609:
2571:
2561:
2521:
1319:
1161:
318:
2302:
2202:
1736:
947:
423:
2659:
2011:
1543:
1166:
982:
338:
2715:. Dept. of Computer Science & Engineering University of California at San Diego: 2002.
1240:
Nevertheless, the general notion of negligibility doesn't require that the input parameter
330:
2623:
2516:
1987:
1637:
1472:
1283:
1263:
1243:
1220:
1200:
1180:
760:
17:
1666:
2733:
2660:
712:
310:
2603:
1156:
342:
314:
1078:
305:
can find its trace back to sound models of analysis. Though the concepts of "
2575:
1303:
The reciprocal-of-polynomial formulation is used for the same reason that
1330:
One of the reasons that negligible functions are used in foundations of
1217:. Hence comes the definition at the top of the page because key length
345:
also defined as follows (with all numbers in the real number domain
286:{\displaystyle |\mu (x)|<{\frac {1}{\operatorname {poly} (x)}}.}
160:
Equivalently, we may also use the following definition. A function
1334:
cryptography is that they obey closure properties. Specifically,
333:, who wrote in 1817 the modern definition of continuity. Later
1661:
2690:
New
Generalized Functions and Multiplication of Distributions
1165:
if the probability of security failure (e.g., inverting a
2707:
Bellare, Mihir (1997). "A Note on
Negligible Functions".
409:{\displaystyle f:\mathbb {R} {\rightarrow }\mathbb {R} }
1678:
2447:
2392:
2332:
2305:
2232:
2205:
2134:
2075:
2040:
2014:
1990:
1936:
1871:
1818:
1767:
1739:
1703:
1640:
1588:
1552:
1495:
1475:
1439:
1386:
1344:
1286:
1266:
1246:
1223:
1203:
1183:
1113:
1087:
1051:
1011:
985:
950:
924:
870:
836:
809:
783:
763:
723:
666:
633:
560:
511:
485:
459:
426:
384:
351:
230:
166:
101:
36:
2627:
2605:Foundations of Cryptography: Volume 1, Basic Tools
2499:
2433:{\displaystyle f(n)={\frac {1}{n^{\frac {1}{n}}}}}
2432:
2370:
2317:
2291:
2217:
2191:
2119:
2052:
2026:
1996:
1976:
1920:
1855:
1802:
1751:
1725:
1646:
1626:
1574:
1531:
1481:
1461:
1422:
1372:
1292:
1272:
1252:
1229:
1209:
1189:
1139:
1099:
1069:
1037:
997:
971:
936:
905:
855:
822:
795:
769:
745:
694:
652:
616:
546:
497:
471:
445:
408:
359:
285:
188:
149:
58:
2560:. Lindell, Yehuda (Second ed.). Boca Raton.
2500:{\displaystyle f(n)={\frac {1}{x^{n(\log {n})}}}}
746:{\displaystyle \mu :\mathbb {R} \to \mathbb {R} }
189:{\displaystyle \mu :\mathbb {N} \to \mathbb {R} }
59:{\displaystyle \mu :\mathbb {N} \to \mathbb {R} }
1373:{\displaystyle f,g:\mathbb {N} \to \mathbb {R} }
617:{\displaystyle |f(x)-f(x_{0})|<\varepsilon .}
150:{\displaystyle |\mu (x)|<{\frac {1}{x^{c}}}.}
2532:Gromov's theorem on groups of polynomial growth
1575:{\displaystyle f:\mathbb {N} \to \mathbb {R} }
1462:{\displaystyle f:\mathbb {N} \to \mathbb {R} }
8:
906:{\displaystyle |\mu (x)|<\varepsilon \,.}
2658:(1993). "Section 12.1: One-way functions".
2292:{\displaystyle f(n)=1/x^{({\log {n})}^{k}}}
2588:: CS1 maint: location missing publisher (
1489:is any real polynomial, then the function
1171:cryptographically strong pseudorandom bits
1140:{\displaystyle 1/\operatorname {poly} (x)}
1038:{\displaystyle 1/\operatorname {poly} (x)}
2720:
2692:. Mathematics Studies 84, North Holland.
2666:(1st ed.). Addison Wesley. pp.
2634:Introduction to the Theory of Computation
2485:
2472:
2463:
2446:
2417:
2408:
2391:
2360:
2351:
2331:
2304:
2281:
2272:
2265:
2260:
2251:
2231:
2204:
2192:{\displaystyle f(n)=1/x^{\log {(n^{k})}}}
2177:
2169:
2162:
2153:
2133:
2107:
2103:
2094:
2074:
2039:
2013:
1989:
1956:
1935:
1903:
1870:
1838:
1817:
1791:
1787:
1766:
1738:
1714:
1702:
1639:
1607:
1587:
1568:
1567:
1560:
1559:
1551:
1494:
1474:
1455:
1454:
1447:
1446:
1438:
1385:
1366:
1365:
1358:
1357:
1343:
1285:
1265:
1245:
1222:
1202:
1182:
1117:
1112:
1086:
1050:
1015:
1010:
984:
963:
954:
949:
923:
899:
888:
871:
869:
847:
835:
814:
808:
782:
762:
739:
738:
731:
730:
722:
677:
665:
638:
632:
600:
591:
561:
559:
533:
527:
512:
510:
484:
458:
437:
425:
402:
401:
396:
392:
391:
383:
353:
352:
350:
313:" became important in mathematics during
256:
248:
231:
229:
182:
181:
174:
173:
165:
136:
127:
119:
102:
100:
52:
51:
44:
43:
35:
1318:In practice one might want to have more
1070:{\displaystyle \operatorname {poly} (x)}
2548:
1921:{\displaystyle f(n)=(\log n)^{-\log n}}
1532:{\displaystyle x\mapsto p(x)\cdot f(x)}
1312:
2581:
1803:{\displaystyle f(n)=3^{-{\sqrt {n}}}}
856:{\displaystyle x>N_{\varepsilon }}
66:such that for every positive integer
7:
2371:{\displaystyle f(n)=1/x^{\sqrt {n}}}
547:{\displaystyle |x-x_{0}|<\delta }
211: > 0 such that for all
2629:"Section 10.6.3: One-way functions"
2558:Introduction to modern cryptography
2556:Katz, Johnathan (6 November 2014).
1582:is not negligible, then neither is
2047:
1627:{\displaystyle x\mapsto f(x)/p(x)}
1423:{\displaystyle x\mapsto f(x)+g(x)}
1380:are negligible, then the function
647:
14:
1977:{\displaystyle f(n)=2^{-c\log n}}
1100:{\displaystyle \varepsilon >0}
937:{\displaystyle \varepsilon >0}
796:{\displaystyle \varepsilon >0}
702:, we must define the concept of "
479:, there exists a positive number
472:{\displaystyle \varepsilon >0}
1984:is not negligible, for positive
1856:{\displaystyle f(n)=n^{-\log n}}
1665:
823:{\displaystyle N_{\varepsilon }}
204:poly(·) there exists an integer
1726:{\displaystyle n\mapsto a^{-n}}
777:goes to infinity) if for every
2608:. Cambridge University Press.
2490:
2476:
2457:
2451:
2402:
2396:
2342:
2336:
2277:
2261:
2242:
2236:
2183:
2170:
2144:
2138:
2120:{\displaystyle f(n)=1/x^{n/2}}
2085:
2079:
2044:
1946:
1940:
1900:
1887:
1881:
1875:
1828:
1822:
1777:
1771:
1707:
1621:
1615:
1604:
1598:
1592:
1564:
1526:
1520:
1511:
1505:
1499:
1451:
1417:
1411:
1402:
1396:
1390:
1362:
1134:
1128:
1064:
1058:
1032:
1026:
889:
885:
879:
872:
735:
683:
670:
601:
597:
584:
575:
569:
562:
534:
513:
397:
274:
268:
249:
245:
239:
232:
178:
120:
116:
110:
103:
48:
1:
653:{\displaystyle x_{0}=\infty }
2053:{\displaystyle n\to \infty }
498:{\displaystyle \delta >0}
360:{\displaystyle \mathbb {R} }
2636:. PWS Publishing. pp.
1197:= cryptographic key length
1173:from truly random bits) is
1155:In complexity-based modern
2761:
1237:must be a natural number.
695:{\displaystyle f(x_{0})=0}
15:
1305:computational boundedness
2686:Colombeau, Jean François
2662:Computational Complexity
2602:Goldreich, Oded (2001).
1634:for any real polynomial
70:there exists an integer
16:For a similar term, see
2656:Papadimitriou, Christos
2318:{\displaystyle k\geq 1}
2218:{\displaystyle k\geq 1}
2034:, we take the limit as
1752:{\displaystyle a\geq 2}
1159:, a security scheme is
972:{\displaystyle 1/x^{c}}
446:{\displaystyle x=x_{0}}
2501:
2434:
2372:
2319:
2293:
2219:
2193:
2121:
2054:
2028:
2027:{\displaystyle n>0}
1998:
1978:
1922:
1857:
1804:
1753:
1733:is negligible for any
1727:
1648:
1628:
1576:
1533:
1483:
1463:
1424:
1374:
1294:
1274:
1254:
1231:
1211:
1191:
1177:in terms of the input
1141:
1101:
1071:
1039:
999:
998:{\displaystyle c>0}
973:
938:
907:
857:
824:
797:
771:
747:
717:A continuous function
704:infinitesimal function
696:
654:
618:
548:
499:
473:
447:
410:
361:
287:
190:
151:
60:
2740:Mathematical analysis
2709:Journal of Cryptology
2537:Non-standard calculus
2502:
2435:
2373:
2320:
2294:
2220:
2194:
2122:
2055:
2029:
1999:
1979:
1923:
1858:
1805:
1754:
1728:
1649:
1629:
1577:
1534:
1484:
1464:
1425:
1375:
1295:
1275:
1255:
1232:
1212:
1192:
1142:
1102:
1072:
1040:
1000:
974:
939:
908:
858:
825:
798:
772:
748:
697:
655:
619:
549:
500:
474:
448:
411:
362:
327:mathematical analysis
288:
191:
152:
61:
2445:
2390:
2330:
2303:
2230:
2203:
2132:
2073:
2038:
2012:
1988:
1934:
1869:
1816:
1765:
1737:
1701:
1638:
1586:
1550:
1493:
1473:
1437:
1384:
1342:
1332:complexity-theoretic
1284:
1264:
1244:
1221:
1201:
1181:
1111:
1107:can be expressed as
1085:
1049:
1009:
983:
948:
922:
868:
834:
807:
781:
761:
721:
664:
631:
558:
509:
483:
457:
424:
382:
349:
228:
164:
99:
34:
2527:Nonstandard numbers
1313:#Closure properties
1151:Use in cryptography
374:Continuous function
202:positive polynomial
25:negligible function
2745:Types of functions
2497:
2430:
2368:
2315:
2289:
2215:
2189:
2117:
2050:
2024:
1994:
1974:
1918:
1853:
1800:
1749:
1723:
1677:. You can help by
1644:
1624:
1572:
1529:
1479:
1469:is negligible and
1459:
1420:
1370:
1326:Closure properties
1290:
1270:
1260:is the key length
1250:
1227:
1207:
1187:
1137:
1097:
1067:
1035:
995:
969:
934:
903:
853:
830:such that for all
820:
793:
767:
743:
692:
650:
614:
544:
495:
469:
443:
406:
357:
283:
186:
147:
79:such that for all
56:
23:In mathematics, a
2522:Colombeau algebra
2495:
2428:
2425:
2365:
1997:{\displaystyle c}
1796:
1695:
1694:
1647:{\displaystyle p}
1482:{\displaystyle p}
1293:{\displaystyle x}
1273:{\displaystyle n}
1253:{\displaystyle x}
1230:{\displaystyle n}
1210:{\displaystyle n}
1190:{\displaystyle x}
1169:, distinguishing
944:by the functions
918:Next, we replace
770:{\displaystyle x}
278:
142:
2752:
2726:
2724:
2703:
2681:
2665:
2651:
2631:
2619:
2594:
2593:
2587:
2579:
2553:
2506:
2504:
2503:
2498:
2496:
2494:
2493:
2489:
2464:
2439:
2437:
2436:
2431:
2429:
2427:
2426:
2418:
2409:
2377:
2375:
2374:
2369:
2367:
2366:
2361:
2355:
2324:
2322:
2321:
2316:
2298:
2296:
2295:
2290:
2288:
2287:
2286:
2285:
2280:
2276:
2255:
2224:
2222:
2221:
2216:
2198:
2196:
2195:
2190:
2188:
2187:
2186:
2182:
2181:
2157:
2126:
2124:
2123:
2118:
2116:
2115:
2111:
2098:
2059:
2057:
2056:
2051:
2033:
2031:
2030:
2025:
2003:
2001:
2000:
1995:
1983:
1981:
1980:
1975:
1973:
1972:
1927:
1925:
1924:
1919:
1917:
1916:
1862:
1860:
1859:
1854:
1852:
1851:
1809:
1807:
1806:
1801:
1799:
1798:
1797:
1792:
1758:
1756:
1755:
1750:
1732:
1730:
1729:
1724:
1722:
1721:
1690:
1687:
1669:
1662:
1653:
1651:
1650:
1645:
1633:
1631:
1630:
1625:
1611:
1581:
1579:
1578:
1573:
1571:
1563:
1538:
1536:
1535:
1530:
1488:
1486:
1485:
1480:
1468:
1466:
1465:
1460:
1458:
1450:
1429:
1427:
1426:
1421:
1379:
1377:
1376:
1371:
1369:
1361:
1299:
1297:
1296:
1291:
1279:
1277:
1276:
1271:
1259:
1257:
1256:
1251:
1236:
1234:
1233:
1228:
1216:
1214:
1213:
1208:
1196:
1194:
1193:
1188:
1167:one-way function
1146:
1144:
1143:
1138:
1121:
1106:
1104:
1103:
1098:
1076:
1074:
1073:
1068:
1044:
1042:
1041:
1036:
1019:
1004:
1002:
1001:
996:
978:
976:
975:
970:
968:
967:
958:
943:
941:
940:
935:
912:
910:
909:
904:
892:
875:
862:
860:
859:
854:
852:
851:
829:
827:
826:
821:
819:
818:
802:
800:
799:
794:
776:
774:
773:
768:
752:
750:
749:
744:
742:
734:
701:
699:
698:
693:
682:
681:
659:
657:
656:
651:
643:
642:
623:
621:
620:
615:
604:
596:
595:
565:
553:
551:
550:
545:
537:
532:
531:
516:
504:
502:
501:
496:
478:
476:
475:
470:
452:
450:
449:
444:
442:
441:
415:
413:
412:
407:
405:
400:
395:
366:
364:
363:
358:
356:
292:
290:
289:
284:
279:
277:
257:
252:
235:
215: >
195:
193:
192:
187:
185:
177:
156:
154:
153:
148:
143:
141:
140:
128:
123:
106:
83: >
65:
63:
62:
57:
55:
47:
2760:
2759:
2755:
2754:
2753:
2751:
2750:
2749:
2730:
2729:
2706:
2700:
2684:
2678:
2654:
2648:
2624:Sipser, Michael
2622:
2616:
2601:
2598:
2597:
2580:
2568:
2555:
2554:
2550:
2545:
2513:
2468:
2443:
2442:
2413:
2388:
2387:
2382:Non-negligible:
2356:
2328:
2327:
2301:
2300:
2264:
2256:
2228:
2227:
2201:
2200:
2173:
2158:
2130:
2129:
2099:
2071:
2070:
2036:
2035:
2010:
2009:
1986:
1985:
1952:
1932:
1931:
1899:
1867:
1866:
1834:
1814:
1813:
1783:
1763:
1762:
1735:
1734:
1710:
1699:
1698:
1691:
1685:
1682:
1675:needs expansion
1660:
1636:
1635:
1584:
1583:
1548:
1547:
1491:
1490:
1471:
1470:
1435:
1434:
1382:
1381:
1340:
1339:
1328:
1282:
1281:
1262:
1261:
1242:
1241:
1219:
1218:
1199:
1198:
1179:
1178:
1162:provably secure
1153:
1109:
1108:
1083:
1082:
1047:
1046:
1007:
1006:
981:
980:
959:
946:
945:
920:
919:
866:
865:
843:
832:
831:
810:
805:
804:
779:
778:
759:
758:
719:
718:
673:
662:
661:
634:
629:
628:
587:
556:
555:
523:
507:
506:
481:
480:
455:
454:
433:
422:
421:
380:
379:
347:
346:
331:Bernard Bolzano
301:The concept of
299:
261:
226:
225:
221:
210:
200:, if for every
162:
161:
132:
97:
96:
91:
78:
32:
31:
21:
12:
11:
5:
2758:
2756:
2748:
2747:
2742:
2732:
2731:
2728:
2727:
2722:10.1.1.43.7900
2704:
2698:
2682:
2676:
2652:
2646:
2620:
2614:
2596:
2595:
2566:
2547:
2546:
2544:
2541:
2540:
2539:
2534:
2529:
2524:
2519:
2517:Negligible set
2512:
2509:
2508:
2507:
2492:
2488:
2484:
2481:
2478:
2475:
2471:
2467:
2462:
2459:
2456:
2453:
2450:
2440:
2424:
2421:
2416:
2412:
2407:
2404:
2401:
2398:
2395:
2379:
2378:
2364:
2359:
2354:
2350:
2347:
2344:
2341:
2338:
2335:
2325:
2314:
2311:
2308:
2284:
2279:
2275:
2271:
2268:
2263:
2259:
2254:
2250:
2247:
2244:
2241:
2238:
2235:
2225:
2214:
2211:
2208:
2185:
2180:
2176:
2172:
2168:
2165:
2161:
2156:
2152:
2149:
2146:
2143:
2140:
2137:
2127:
2114:
2110:
2106:
2102:
2097:
2093:
2090:
2087:
2084:
2081:
2078:
2049:
2046:
2043:
2023:
2020:
2017:
2006:
2005:
1993:
1971:
1968:
1965:
1962:
1959:
1955:
1951:
1948:
1945:
1942:
1939:
1929:
1928:is negligible.
1915:
1912:
1909:
1906:
1902:
1898:
1895:
1892:
1889:
1886:
1883:
1880:
1877:
1874:
1864:
1863:is negligible.
1850:
1847:
1844:
1841:
1837:
1833:
1830:
1827:
1824:
1821:
1811:
1810:is negligible.
1795:
1790:
1786:
1782:
1779:
1776:
1773:
1770:
1760:
1748:
1745:
1742:
1720:
1717:
1713:
1709:
1706:
1693:
1692:
1672:
1670:
1659:
1656:
1643:
1623:
1620:
1617:
1614:
1610:
1606:
1603:
1600:
1597:
1594:
1591:
1570:
1566:
1562:
1558:
1555:
1541:
1540:
1539:is negligible.
1528:
1525:
1522:
1519:
1516:
1513:
1510:
1507:
1504:
1501:
1498:
1478:
1457:
1453:
1449:
1445:
1442:
1431:
1430:is negligible.
1419:
1416:
1413:
1410:
1407:
1404:
1401:
1398:
1395:
1392:
1389:
1368:
1364:
1360:
1356:
1353:
1350:
1347:
1327:
1324:
1289:
1269:
1249:
1226:
1206:
1186:
1152:
1149:
1136:
1133:
1130:
1127:
1124:
1120:
1116:
1096:
1093:
1090:
1077:is a positive
1066:
1063:
1060:
1057:
1054:
1034:
1031:
1028:
1025:
1022:
1018:
1014:
994:
991:
988:
966:
962:
957:
953:
933:
930:
927:
916:
915:
914:
913:
902:
898:
895:
891:
887:
884:
881:
878:
874:
850:
846:
842:
839:
817:
813:
792:
789:
786:
766:
741:
737:
733:
729:
726:
691:
688:
685:
680:
676:
672:
669:
649:
646:
641:
637:
625:
624:
613:
610:
607:
603:
599:
594:
590:
586:
583:
580:
577:
574:
571:
568:
564:
543:
540:
536:
530:
526:
522:
519:
515:
494:
491:
488:
468:
465:
462:
440:
436:
432:
429:
404:
399:
394:
390:
387:
355:
298:
295:
294:
293:
282:
276:
273:
270:
267:
264:
260:
255:
251:
247:
244:
241:
238:
234:
219:
208:
184:
180:
176:
172:
169:
158:
157:
146:
139:
135:
131:
126:
122:
118:
115:
112:
109:
105:
87:
74:
54:
50:
46:
42:
39:
18:negligible set
13:
10:
9:
6:
4:
3:
2:
2757:
2746:
2743:
2741:
2738:
2737:
2735:
2723:
2718:
2714:
2710:
2705:
2701:
2699:0-444-86830-5
2695:
2691:
2687:
2683:
2679:
2677:0-201-53082-1
2673:
2669:
2664:
2663:
2657:
2653:
2649:
2647:0-534-94728-X
2643:
2639:
2635:
2630:
2625:
2621:
2617:
2615:0-521-79172-3
2611:
2607:
2606:
2600:
2599:
2591:
2585:
2577:
2573:
2569:
2567:9781466570269
2563:
2559:
2552:
2549:
2542:
2538:
2535:
2533:
2530:
2528:
2525:
2523:
2520:
2518:
2515:
2514:
2510:
2486:
2482:
2479:
2473:
2469:
2465:
2460:
2454:
2448:
2441:
2422:
2419:
2414:
2410:
2405:
2399:
2393:
2386:
2385:
2384:
2383:
2362:
2357:
2352:
2348:
2345:
2339:
2333:
2326:
2312:
2309:
2306:
2282:
2273:
2269:
2266:
2257:
2252:
2248:
2245:
2239:
2233:
2226:
2212:
2209:
2206:
2178:
2174:
2166:
2163:
2159:
2154:
2150:
2147:
2141:
2135:
2128:
2112:
2108:
2104:
2100:
2095:
2091:
2088:
2082:
2076:
2069:
2068:
2067:
2065:
2061:
2041:
2021:
2018:
2015:
1991:
1969:
1966:
1963:
1960:
1957:
1953:
1949:
1943:
1937:
1930:
1913:
1910:
1907:
1904:
1896:
1893:
1890:
1884:
1878:
1872:
1865:
1848:
1845:
1842:
1839:
1835:
1831:
1825:
1819:
1812:
1793:
1788:
1784:
1780:
1774:
1768:
1761:
1746:
1743:
1740:
1718:
1715:
1711:
1704:
1697:
1696:
1689:
1680:
1676:
1673:This section
1671:
1668:
1664:
1663:
1657:
1655:
1641:
1618:
1612:
1608:
1601:
1595:
1589:
1556:
1553:
1545:
1523:
1517:
1514:
1508:
1502:
1496:
1476:
1443:
1440:
1432:
1414:
1408:
1405:
1399:
1393:
1387:
1354:
1351:
1348:
1345:
1337:
1336:
1335:
1333:
1325:
1323:
1321:
1316:
1314:
1311:setting (see
1310:
1306:
1301:
1287:
1267:
1247:
1238:
1224:
1204:
1184:
1176:
1172:
1168:
1164:
1163:
1158:
1150:
1148:
1131:
1125:
1122:
1118:
1114:
1094:
1091:
1088:
1080:
1061:
1055:
1052:
1029:
1023:
1020:
1016:
1012:
992:
989:
986:
964:
960:
955:
951:
931:
928:
925:
900:
896:
893:
882:
876:
864:
863:
848:
844:
840:
837:
815:
811:
803:there exists
790:
787:
784:
764:
756:
755:infinitesimal
727:
724:
716:
714:
713:Infinitesimal
709:
708:
707:
705:
689:
686:
678:
674:
667:
644:
639:
635:
611:
608:
605:
592:
588:
581:
578:
572:
566:
541:
538:
528:
524:
520:
517:
492:
489:
486:
466:
463:
460:
453:if for every
438:
434:
430:
427:
419:
388:
385:
377:
375:
370:
369:
368:
344:
340:
336:
332:
328:
324:
320:
316:
312:
311:infinitesimal
308:
304:
303:negligibility
296:
280:
271:
265:
262:
258:
253:
242:
236:
224:
223:
222:
218:
214:
207:
203:
199:
170:
167:
144:
137:
133:
129:
124:
113:
107:
95:
94:
93:
90:
86:
82:
77:
73:
69:
40:
37:
30:
26:
19:
2712:
2708:
2689:
2661:
2633:
2604:
2557:
2551:
2381:
2380:
2063:
2062:
2007:
1683:
1679:adding to it
1674:
1542:
1329:
1317:
1302:
1239:
1174:
1160:
1157:cryptography
1154:
917:
754:
710:
703:
626:
417:
371:
322:
302:
300:
216:
212:
205:
197:
159:
88:
84:
80:
75:
71:
67:
24:
22:
1280:. Indeed,
378:A function
339:Weierstrass
329:was due to
2734:Categories
2543:References
2064:Negligible
1686:March 2018
1544:Conversely
1309:asymptotic
1175:negligible
1079:polynomial
505:such that
418:continuous
323:continuity
307:continuity
198:negligible
2717:CiteSeerX
2584:cite book
2576:893721520
2483:
2310:≥
2270:
2210:≥
2167:
2048:∞
2045:→
1967:
1958:−
1911:
1905:−
1894:
1846:
1840:−
1789:−
1744:≥
1716:−
1708:↦
1593:↦
1565:→
1515:⋅
1500:↦
1452:→
1391:↦
1363:→
1126:
1089:ε
1056:
1024:
926:ε
897:ε
877:μ
849:ε
816:ε
785:ε
736:→
725:μ
648:∞
609:ε
579:−
542:δ
521:−
487:δ
461:ε
398:→
266:
237:μ
179:→
168:μ
108:μ
49:→
38:μ
2688:(1984).
2626:(1997).
2511:See also
1658:Examples
1320:concrete
554:implies
29:function
2638:374–376
2008:Assume
319:Leibniz
309:" and "
297:History
2719:
2696:
2674:
2670:–298.
2644:
2612:
2574:
2564:
1045:where
1005:or by
979:where
335:Cauchy
315:Newton
1546:, if
660:with
343:Heine
27:is a
2694:ISBN
2672:ISBN
2642:ISBN
2610:ISBN
2590:link
2572:OCLC
2562:ISBN
2299:for
2199:for
2019:>
1123:poly
1092:>
1053:poly
1021:poly
990:>
929:>
894:<
841:>
788:>
757:(as
606:<
539:<
490:>
464:>
341:and
317:and
263:poly
254:<
220:poly
209:poly
125:<
2668:279
2480:log
2267:log
2164:log
1964:log
1908:log
1891:log
1843:log
1681:.
1433:If
1338:If
753:is
706:":
420:at
416:is
367:):
325:in
196:is
2736::
2713:15
2711:.
2640:.
2632:.
2586:}}
2582:{{
2570:.
2066::
2060::
1654:.
337:,
92:,
2725:.
2702:.
2680:.
2650:.
2618:.
2592:)
2578:.
2491:)
2487:n
2477:(
2474:n
2470:x
2466:1
2461:=
2458:)
2455:n
2452:(
2449:f
2423:n
2420:1
2415:n
2411:1
2406:=
2403:)
2400:n
2397:(
2394:f
2363:n
2358:x
2353:/
2349:1
2346:=
2343:)
2340:n
2337:(
2334:f
2313:1
2307:k
2283:k
2278:)
2274:n
2262:(
2258:x
2253:/
2249:1
2246:=
2243:)
2240:n
2237:(
2234:f
2213:1
2207:k
2184:)
2179:k
2175:n
2171:(
2160:x
2155:/
2151:1
2148:=
2145:)
2142:n
2139:(
2136:f
2113:2
2109:/
2105:n
2101:x
2096:/
2092:1
2089:=
2086:)
2083:n
2080:(
2077:f
2042:n
2022:0
2016:n
2004:.
1992:c
1970:n
1961:c
1954:2
1950:=
1947:)
1944:n
1941:(
1938:f
1914:n
1901:)
1897:n
1888:(
1885:=
1882:)
1879:n
1876:(
1873:f
1849:n
1836:n
1832:=
1829:)
1826:n
1823:(
1820:f
1794:n
1785:3
1781:=
1778:)
1775:n
1772:(
1769:f
1759:.
1747:2
1741:a
1719:n
1712:a
1705:n
1688:)
1684:(
1642:p
1622:)
1619:x
1616:(
1613:p
1609:/
1605:)
1602:x
1599:(
1596:f
1590:x
1569:R
1561:N
1557::
1554:f
1527:)
1524:x
1521:(
1518:f
1512:)
1509:x
1506:(
1503:p
1497:x
1477:p
1456:R
1448:N
1444::
1441:f
1418:)
1415:x
1412:(
1409:g
1406:+
1403:)
1400:x
1397:(
1394:f
1388:x
1367:R
1359:N
1355::
1352:g
1349:,
1346:f
1288:x
1268:n
1248:x
1225:n
1205:n
1185:x
1135:)
1132:x
1129:(
1119:/
1115:1
1095:0
1065:)
1062:x
1059:(
1033:)
1030:x
1027:(
1017:/
1013:1
993:0
987:c
965:c
961:x
956:/
952:1
932:0
901:.
890:|
886:)
883:x
880:(
873:|
845:N
838:x
812:N
791:0
765:x
740:R
732:R
728::
715:)
711:(
690:0
687:=
684:)
679:0
675:x
671:(
668:f
645:=
640:0
636:x
612:.
602:|
598:)
593:0
589:x
585:(
582:f
576:)
573:x
570:(
567:f
563:|
535:|
529:0
525:x
518:x
514:|
493:0
467:0
439:0
435:x
431:=
428:x
403:R
393:R
389::
386:f
376:)
372:(
354:R
281:.
275:)
272:x
269:(
259:1
250:|
246:)
243:x
240:(
233:|
217:N
213:x
206:N
183:R
175:N
171::
145:.
138:c
134:x
130:1
121:|
117:)
114:x
111:(
104:|
89:c
85:N
81:x
76:c
72:N
68:c
53:R
45:N
41::
20:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
