عدد نرم

عدد نرم (به انگلیسی: Smooth number و گاهی n-friable number) در نظریه اعداد به عددی صحیح گفته می‌شود که تمام مقسوم‌علیه‌های اول آن کمتر یا مساوی عدد n مشخصی باشند.^[۱]^[۲] برای مثال، یک عدد۷-نرم، عددی است که هر عامل اول آن حداکثر ۷ باشد. بر این اساس، ۴۹ = ۷^۲ و ۱۵۷۵۰ = ۲ × ۳^۲ × ۵^۳ × ۷ هر دو ۷-نرم هستند، در حالی که ۱۱ و ۷۰۲ = ۲ × ۳^۳ × ۱۳ ۷-نرم نیستند. به نظر می‌رسد این اصطلاح توسط لئونارد آدلمن ابداع شده باشد. ^[۳]

اعداد نرم به ویژه در رمزنگاری اهمیت دارند، چرا که رمزنگاری تجزیه اعداد صحیح به عوامل اول وابسته است. اعداد ۲-نرم صرفاً توان‌هایی از عدد ۲ هستند، در حالی که اعداد ۵-نرم با عنوان اعداد منظم نیز شناخته می‌شوند.

تعریف

عدد صحیح مثبت B-نرم نامیده می‌شود اگر هیچ‌یک از عوامل اول آن بزرگ‌تر از B نباشد. برای مثال، ۱۶۲۰ دارای تجزیه به عوامل اول ۲^۲ × ۳^۴ × ۵ است؛ بنابراین ۱۶۲۰ یک عدد ۵-نرم است، زیرا هیچ‌یک از عوامل اول آن بزرگ‌تر از ۵ نیستند. این تعریف شامل اعدادی می‌شود که برخی از عوامل اول کوچک‌تر را ندارند؛ به عنوان مثال، هم ۱۰ و هم ۱۲ عدد ۵-نرم هستند، حتی با وجود آنکه به ترتیب فاقد عوامل اول ۳ و ۵ می‌باشند. تمام اعداد ۵-نرم به صورت ۲^a × ۳^b × ۵^c هستند، که در آن a, b و c اعداد صحیح نامنفی می‌باشند.
اعداد ۳-نرم با نام «اعداد هارمونیک» نیز شناخته شده‌اند ^[۴]، هرچند این نام معانی رایج‌تری نیز دارد، به‌ویژه برای مجموع معکوس اعداد طبیعی. اعداد ۵-نرم را همچنین «اعداد منظم» یا «اعداد همینگ» نیز می‌نامند ^[۵]؛ اعداد ۷-نرم نیز به نام «اعداد فروتن» شناخته می‌شوند^[۶] و گاهی «اعداد بسیار ترکیبی» خوانده می‌شوند^[۷]، اگرچه این اصطلاح با معنای دیگری از اعداد بسیار ترکیبی در تعارض است.
در اینجا باید توجه داشت که لزوماً B نباید در میان عوامل یک عدد B-نرم ظاهر شود. اگر بزرگترین عامل اول یک عدد p باشد، آنگاه این عدد برای هر B ≥ p، B-نرم است. در بسیاری از سناریوها B یک عدد اول است، اما اعداد مرکب نیز مجاز هستند. یک عدد B-نرم است اگر و تنها اگر p-نرم باشد، که در آن p بزرگترین عدد اول کمتر یا مساوی B است.

کاربردها

یکی از کاربردهای مهم و عملی اعداد نرم، در الگوریتم‌های تبدیل فوریه سریع (FFT) (مانند الگوریتم FFT کولای-توکی) است. این الگوریتم‌ها با شکستن بازگشتی یک مسئله با اندازهٔ n به مسائل کوچکتر به اندازهٔ عوامل آن کار می‌کنند. با استفاده از اعداد B-نرم، اطمینان حاصل می‌شود که حالت‌های پایه این بازگشت، اعداد اول کوچکی هستند که الگوریتم‌های کارآمدی برای آن‌ها وجود دارد. (اندازه‌های اول بزرگ‌تر به الگوریتم‌های کم‌بازده‌تری مانند الگوریتم FFT بلواستاین نیاز دارند.)
اعداد ۵-نرم یا اعداد منظم نقش ویژه‌ای در ریاضیات بابلیان ایفا می‌کنند ^[۸]. آن‌ها همچنین در نظریه موسیقی مهم هستند (به حد (موسیقی) مراجعه کنید)^[۹] و مسئلهٔ تولید کارآمد این اعداد به عنوان یک مسئلهٔ آزمایشی برای برنامه‌نویسی تابعی استفاده شده است ^[۱۰].
اعداد نرم کاربردهای متعددی در رمزنگاری دارند ^[۱۱]. اگرچه بیشتر این کاربردها حول محور رمزشکنی است (مثلاً سریع‌ترین الگوریتم‌های شناخته‌شده برای تجزیه اعداد صحیح مانند غربال عمومی میدان اعداد)، تابع هش VSH نمونه‌ای دیگر از استفادهٔ سازنده از خاصیت نرم بودن اعداد برای دستیابی به طراحی اثباتاً امن است.

توزیع

فرض کنید Ψ(x, y) تعداد اعداد صحیح مثبت y-نرم کمتر مساوی x را نشان دهد (تابع دو برویین).

اگر کران نرم بودن B ثابت و کوچک باشد، برآورد خوبی برای Ψ(x, B) وجود دارد:

\Psi (x,B)\sim {\frac {1}{\pi (B)!}}\prod _{p\leq B}{\frac {\log x}{\log p}}

که در آن π(B) تعداد اعداد اول کمتر مساوی B است.

در غیر این صورت، پارامتر u را به صورت u = \log x / \log y تعریف می‌کنیم، یعنی x = y^u. در این حالت:

\Psi (x,y)=x\cdot \rho (u)+O\left({\frac {x}{\log y}}\right)

که در آن ρ(u) تابع دیکمن است.

برای هر k، تقریباً همه‌ی اعداد طبیعی، k-نرم نخواهند بود.

اگر n = n₁ n₂، به‌گونه‌ای که n₁، B-نرم و n₂ غیر B-نرم (یا برابر با ۱) باشد، آن‌گاه n₁ را بخش B-نرم عدد n می‌نامند. اندازه‌ی نسبی بخش x^{1/u}-نرم یک عدد صحیح تصادفی کوچکتر یا مساوی x، به‌صورت قابل توجهی کندتر از ρ(u) کاهش می‌یابد ^[۱۲].

اعداد توان‌نرم

عدد m را n-توان‌نرم (یا n-اولترافریبل) می‌نامند اگر همهٔ توان‌های اول p^ν که m را تقسیم می‌کنند، داشته باشند:

p^{\nu }\leq n

برای مثال، عدد ۷۲۰ (۲^۴ × ۳^۲ × ۵) یک عدد ۵-نرم است اما ۵-توان‌نرم نیست (زیرا چندین توانِ اول آن از ۵ بزرگ‌ترند؛ مثلاً $3^{2}=9\nleq 5$ و $2^{4}=16\nleq 5$ ). این عدد ۱۶-توان‌نرم است چرا که بزرگ‌ترین توانِ عامل اول آن $2^{4}=16$ است. همچنین این عدد ۱۷-توان‌نرم، ۱۸-توان‌نرم و ... نیز هست.

برخلاف اعداد n-نرم، برای هر عدد صحیح مثبت n فقط تعداد متناهی‌ای عدد n-توان‌نرم وجود دارد؛ در واقع، این اعداد دقیقاً مقسوم‌علیه‌های مثبتِ «کوچک‌ترین مضرب مشترک اعداد ۱، ۲، ۳، … ، n» (دنباله A003418 در پایگاه دنباله‌های صحیح آنلاین) هستند؛ برای نمونه، اعداد ۹-توان‌نرم (همچنین اعداد ۱۰-توان‌نرم) دقیقاً مقسوم‌علیه‌های مثبت ۲۵۲۰ هستند.

اعداد n-نرم و n-توان‌نرم در نظریه اعداد کاربرد دارند، مانند الگوریتم p-۱ پولارد و ECM. در چنین کاربردهایی معمولاً گفته می‌شود الگوریتم برای «اعداد نرم» کار می‌کند، بدون مشخص‌کردن n؛ یعنی باید اعداد مورد نظر n-توان‌نرم برای مقداری کوچک از n باشند. با افزایش n، کارایی الگوریتم یا روش مورد بحث به‌سرعت کاهش می‌یابد. برای مثال،الگوریتم پولیگ–هلمن برای محاسبه لگاریتم گسسته دارای زمان اجرای $O(n^{1/2})$ (نماد O بزرگ)برای گروه‌هایی با مرتبهٔ n-نرم است.

نرم بودن نسبت به یک مجموعه A

اگر بتوان عدد $m$ را طوری تجزیه کرد که هر عامل این تجزیه، توان صحیحی از اعضای یک مجموعه $A$ باشد، گفته می‌شود $m$ نسبت به مجموعه $A$ نرم است. برای مثال، چون $12=4\times 3$ ، عدد ۱۲ نسبت به مجموعه‌های $A_{1}=\{4,\,3\}$ ، $A_{2}=\{2,\,3\}$ و همچنین نسبت به مجموعه اعداد صحیح $\mathbb {Z}$ نرم است؛ اما نسبت به مجموعه $A_{3}=\{3,\,5\}$ نرم نیست، زیرا ۱۲ دارای عامل $4=2^{2}$ است و هیچ‌یک از ۴ یا ۲ در $A_{3}$ وجود ندارند. وجه داشته باشید که مجموعهٔ $A$ الزاماً نباید مجموعه‌ای از اعداد اول باشد؛ اما معمولاً یک زیرمجموعهٔ خاص از اعداد اول است، همان‌طور که در پایهٔ فاکتورگیری در روش دیکسون و غربال مربعی مشاهده می‌شود. به همین ترتیب، همین مفهوم در غربال عمومی میدان اعداد برای تعریف نرم بودن به کار می‌رود، تحت همریختی ${\displaystyle \varphi$ .^[۱۳]

جستارهای وابسته

عدد بسیار ترکیبی
عدد زبر
عدد رُند
قضیه استورمر
عدد غیرمعمول

منابع

^[۱] ^[۲] ^[۳] ^[۴] ^[۵] ^[۶] ^[۷] ^[۸] ^[۹] ^[۱۰] ^[۱۱] ^[۱۲] ^[۱۳]>

کتاب‌شناسی

G. Tenenbaum, Introduction to analytic and probabilistic number theory, (AMS, 2015), ISBN 978-0821898543.
A. Granville, Smooth numbers: Computational number theory and beyond, مجموعه مقالات کارگاه MSRI، ۲۰۰۸.

پیوند به بیرون

Weisstein, Eric W. "Smooth Number". MathWorld.
پایگاه دنباله‌های اعداد صحیح آنلاین (OEIS)، فهرستی از اعداد نرم B-تایی برای مقادیر کوچک B:
- ۲-نرم: A000079
- ۳-نرم: A003586
- ۵-نرم: A051037
- ۷-نرم: A002473
- ۱۱-نرم: A051038
- ۱۳-نرم: A080197
- ۱۷-نرم: A080681
- ۱۹-نرم: A080682
- ۲۳-نرم: A080683

1 2 "P-Smooth Numbers or P-friable Number". GeeksforGeeks. 2018-02-12. دریافت‌شده در 2019-12-12.
1 2 Weisstein, Eric W. "Smooth Number". mathworld.wolfram.com. دریافت‌شده در 2019-12-12.
1 2 Hellman, M. E.; Reyneri, J. M. (1983). "Fast Computation of Discrete Logarithms in GF (q)". Advances in Cryptology – Proceedings of Crypto 82. pp. 3–13. doi:10.1007/978-1-4757-0602-4_1. ISBN 978-1-4757-0604-8.
1 2 Sloane, N. J. A. (ed.). "Sequence A003586 (3-smooth numbers)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
1 2 "Python: Get the Hamming numbers upto a given numbers also check whether a given number is an Hamming number". w3resource. دریافت‌شده در 2019-12-12.
1 2 "Problem H: Humble Numbers". www.eecs.qmul.ac.uk. دریافت‌شده در 2019-12-12.
1 2 Sloane, N. J. A. (ed.). "Sequence A002473 (7-smooth numbers)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
1 2 Aaboe, Asger (1965), "Some Seleucid mathematical tables (extended reciprocals and squares of regular numbers)", Journal of Cuneiform Studies, 19 (3): 79–86, doi:10.2307/1359089, JSTOR 1359089, MR 0191779, S2CID 164195082.
1 2 Longuet-Higgins, H. C. (1962), "Letter to a musical friend", Music Review (August): 244–248.
1 2 Dijkstra, Edsger W. (1981), Hamming's exercise in SASL (PDF), Report EWD792. Originally a privately circulated handwritten note.
1 2 Naccache, David; Shparlinski, Igor (17 October 2008). "Divisibility, Smoothness and Cryptographic Applications" (PDF). eprint.iacr.org. arXiv:0810.2067. دریافت‌شده در 26 July 2017.
1 2 Kim, Taechan; Tibouchi, Mehdi (2015). "Invalid Curve Attacks in a GLS Setting". In Tanaka, Keisuke; Suga, Yuji (eds.). Advances in Information and Computer Security – 10th International Workshop on Security, IWSEC 2015, Nara, Japan, August 26–28, 2015, Proceedings. Lecture Notes in Computer Science. Vol. 9241. Springer. pp. 41–55. doi:10.1007/978-3-319-22425-1_3. ISBN 978-3-319-22424-4.
1 2 Briggs, Matthew E. (17 April 1998). "An Introduction to the General Number Field Sieve" (PDF). math.vt.edu. Blacksburg, Virginia: Virginia Polytechnic Institute and State University. دریافت‌شده در 26 July 2017.

[PSmooth-1] 1 2 "P-Smooth Numbers or P-friable Number". GeeksforGeeks. 2018-02-12. دریافت‌شده در 2019-12-12.

[Weisstein-2] 1 2 Weisstein, Eric W. "Smooth Number". mathworld.wolfram.com. دریافت‌شده در 2019-12-12.

[Hellman-3] 1 2 Hellman, M. E.; Reyneri, J. M. (1983). "Fast Computation of Discrete Logarithms in GF (q)". Advances in Cryptology – Proceedings of Crypto 82. pp. 3–13. doi:10.1007/978-1-4757-0602-4_1. ISBN 978-1-4757-0604-8.

[OEISA003586-4] 1 2 Sloane, N. J. A. (ed.). "Sequence A003586 (3-smooth numbers)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.

[w3resource-5] 1 2 "Python: Get the Hamming numbers upto a given numbers also check whether a given number is an Hamming number". w3resource. دریافت‌شده در 2019-12-12.

[HumbleQMU-6] 1 2 "Problem H: Humble Numbers". www.eecs.qmul.ac.uk. دریافت‌شده در 2019-12-12.

[OEISA002473-7] 1 2 Sloane, N. J. A. (ed.). "Sequence A002473 (7-smooth numbers)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.

[Aaboe-8] 1 2 Aaboe, Asger (1965), "Some Seleucid mathematical tables (extended reciprocals and squares of regular numbers)", Journal of Cuneiform Studies, 19 (3): 79–86, doi:10.2307/1359089, JSTOR 1359089, MR 0191779, S2CID 164195082.

[LonguetHiggins-9] 1 2 Longuet-Higgins, H. C. (1962), "Letter to a musical friend", Music Review (August): 244–248.

[Dijkstra-10] 1 2 Dijkstra, Edsger W. (1981), Hamming's exercise in SASL (PDF), Report EWD792. Originally a privately circulated handwritten note.

[Naccache-11] 1 2 Naccache, David; Shparlinski, Igor (17 October 2008). "Divisibility, Smoothness and Cryptographic Applications" (PDF). eprint.iacr.org. arXiv:0810.2067. دریافت‌شده در 26 July 2017.

[KimTibouchi-12] 1 2 Kim, Taechan; Tibouchi, Mehdi (2015). "Invalid Curve Attacks in a GLS Setting". In Tanaka, Keisuke; Suga, Yuji (eds.). Advances in Information and Computer Security – 10th International Workshop on Security, IWSEC 2015, Nara, Japan, August 26–28, 2015, Proceedings. Lecture Notes in Computer Science. Vol. 9241. Springer. pp. 41–55. doi:10.1007/978-3-319-22425-1_3. ISBN 978-3-319-22424-4.

[Briggs-13] 1 2 Briggs, Matthew E. (17 April 1998). "An Introduction to the General Number Field Sieve" (PDF). math.vt.edu. Blacksburg, Virginia: Virginia Polytechnic Institute and State University. دریافت‌شده در 26 July 2017.

[۱]