موضوع مقاله: عدد نرم | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # عدد نرم | مقدمه: بر این اساس، ۴۹ = ۷۲ و ۱۵۷۵۰ = ۲ × ۳۲ × ۵۳ × ۷ هر دو ۷-نرم هستند، در حالی که ۱۱ و ۷۰۲ = ۲ × ۳۳ × ۱۳ ۷-نرم نیستند. | ## بخش 1: عدد نرم | اعداد نرم به ویژه در رمزنگاری اهمیت دارند، چرا که رمزنگاری تجزیه اعداد صحیح به عوامل اول وابسته است. اعداد ۲-نرم صرفاً توان‌هایی از عدد ۲ هستند، در حالی که اعداد ۵-نرم با عنوان اعداد منظم نیز شناخته می‌شوند. تعریف عدد صحیح مثبت B-نرم نامیده می‌شود اگر هیچ‌یک از عوامل اول آن بزرگ‌تر از B نباشد. برای مثال، ۱۶۲۰ دارای تجزیه به عوامل اول ۲۲ × ۳۴ × ۵ است؛ بنابراین ۱۶۲۰ یک عدد ۵-نرم است، زیرا هیچ‌یک از عوامل اول آن بزرگ‌تر از ۵ نیستند. این تعریف شامل اعدادی می‌شود که برخی از عوامل اول کوچک‌تر را ندارند؛ به عنوان مثال، هم ۱۰ و هم ۱۲ عدد ۵-نرم هستند، حتی با وجود آنکه به ترتیب فاقد عوامل اول ۳ و ۵ می‌باشند. تمام اعداد ۵-نرم به صورت ۲a × ۳b × ۵c هستند، که در آن a, b و c اعداد صحیح نامنفی می‌باشند. اعداد ۳-نرم با نام «اعداد هارمونیک» نیز شناخته شده‌اند ، هرچند این نام معانی رایج‌تری نیز دارد، به‌ویژه برای مجموع معکوس اعداد طبیعی. اعداد ۵-نرم را همچنین «اعداد منظم» یا «اعداد همینگ» نیز می‌نامند ؛ اعداد ۷-نرم نیز به نام «اعداد فروتن» شناخته می‌شوند و گاهی «اعداد بسیار ترکیبی» خوانده می‌شوند، اگرچه این اصطلاح با معنای دیگری از اعداد بسیار ترکیبی در تعارض است. یک عدد B-نرم است اگر و تنها اگر p-نرم باشد، که در آن p بزرگترین عدد اول کمتر یا مساوی B است. | ## بخش 2: عدد نرم | کاربردها یکی از کاربردهای مهم و عملی اعداد نرم، در الگوریتم‌های تبدیل فوریه سریع (FFT) (مانند الگوریتم FFT کولای-توکی) است. این الگوریتم‌ها با شکستن بازگشتی یک مسئله با اندازهٔ n به مسائل کوچکتر به اندازهٔ عوامل آن کار می‌کنند. با استفاده از اعداد B-نرم، اطمینان حاصل می‌شود که حالت‌های پایه این بازگشت، اعداد اول کوچکی هستند که الگوریتم‌های کارآمدی برای آن‌ها وجود دارد. (اندازه‌های اول بزرگ‌تر به الگوریتم‌های کم‌بازده‌تری مانند الگوریتم FFT بلواستاین نیاز دارند.) اعداد ۵-نرم یا اعداد منظم نقش ویژه‌ای در ریاضیات بابلیان ایفا می‌کنند . آن‌ها همچنین در نظریه موسیقی مهم هستند (به حد (موسیقی) مراجعه کنید) و مسئلهٔ تولید کارآمد این اعداد به عنوان یک مسئلهٔ آزمایشی برای برنامه‌نویسی تابعی استفاده شده است . اگرچه بیشتر این کاربردها حول محور رمزشکنی است (مثلاً سریع‌ترین الگوریتم‌های شناخته‌شده برای تجزیه اعداد صحیح مانند غربال عمومی میدان اعداد)، تابع هش VSH نمونه‌ای دیگر از استفادهٔ سازنده از خاصیت نرم بودن اعداد برای دستیابی به طراحی اثباتاً امن است. توزیع فرض کنید Ψ(x, y) تعداد اعداد صحیح مثبت y-نرم کمتر مساوی x را نشان دهد (تابع دو برویین). اگر کران نرم بودن B ثابت و کوچک باشد، برآورد خوبی برای Ψ(x, B) وجود دارد: که در آن π(B) تعداد اعداد اول کمتر مساوی B است. اندازه‌ی نسبی بخش x^{1/u}-نرم یک عدد صحیح تصادفی کوچکتر یا مساوی x، به‌صورت قابل توجهی کندتر از ρ(u) کاهش می‌یابد . | ## بخش 3: عدد نرم | اعداد توان‌نرم عدد m را n-توان‌نرم (یا n-اولترافریبل) می‌نامند اگر همهٔ توان‌های اول p^ν که m را تقسیم می‌کنند، داشته باشند: برای مثال، عدد ۷۲۰ (۲۴ × ۳۲ × ۵) یک عدد ۵-نرم است اما ۵-توان‌نرم نیست (زیرا چندین توانِ اول آن از ۵ بزرگ‌ترند؛ مثلاً و ). برخلاف اعداد n-نرم، برای هر عدد صحیح مثبت n فقط تعداد متناهی‌ای عدد n-توان‌نرم وجود دارد؛ در واقع، این اعداد دقیقاً مقسوم‌علیه‌های مثبتِ «کوچک‌ترین مضرب مشترک اعداد ۱، ۲، ۳، … ، n» (دنباله A003418 در پایگاه دنباله‌های صحیح آنلاین) هستند؛ برای نمونه، اعداد ۹-توان‌نرم (همچنین اعداد ۱۰-توان‌نرم) دقیقاً مقسوم‌علیه‌های مثبت ۲۵۲۰ هستند. اعداد n-نرم و n-توان‌نرم در نظریه اعداد کاربرد دارند، مانند الگوریتم p-۱ پولارد و ECM. در چنین کاربردهایی معمولاً گفته می‌شود الگوریتم برای «اعداد نرم» کار می‌کند، بدون مشخص‌کردن n؛ یعنی باید اعداد مورد نظر n-توان‌نرم برای مقداری کوچک از n باشند. برای مثال،الگوریتم پولیگ–هلمن برای محاسبه لگاریتم گسسته دارای زمان اجرای (نماد O بزرگ)برای گروه‌هایی با مرتبهٔ n-نرم است. نرم بودن نسبت به یک مجموعه A اگر بتوان عدد را طوری تجزیه کرد که هر عامل این تجزیه، توان صحیحی از اعضای یک مجموعه باشد، گفته می‌شود نسبت به مجموعه نرم است. برای مثال، چون ، عدد ۱۲ نسبت به مجموعه‌های، و همچنین نسبت به مجموعه اعداد صحیح نرم است؛ اما نسبت به مجموعه نرم نیست، زیرا ۱۲ دارای عامل است و هیچ‌یک از ۴ یا ۲ در وجود ندارند. وجه داشته باشید که مجموعهٔ الزاماً نباید مجموعه‌ای از اعداد اول باشد؛ اما معمولاً یک زیرمجموعهٔ خاص از اعداد اول است، همان‌طور که در پایهٔ فاکتورگیری در روش دیکسون و غربال مربعی مشاهده می‌شود. | ## جمع‌بندی | به همین ترتیب، همین مفهوم در غربال عمومی میدان اعداد برای تعریف نرم بودن به کار می‌رود، تحت همریختی.