صفحه 2 از 5

Re: آیا اعداد اول فرمول دارند؟

ارسال شده: دوشنبه ۱۳۹۳/۷/۱۴ - ۱۵:۴۹
توسط You-See
ایشون ادعا کردن برنامشون تا هر رقمی جواب می ده. لطف کنند بگند که برای عدد 256 رقمی مورد استفاده در تراکنش های مالی بانک ها، چقدر طول می کشه؟ اگر زمان ایشون زیر یک ماه بود، من دیگه برنامه نویسی نمی کنم.

دوستان بلد نیستید چیزی رو هم ادعا نکنید.
اعداد اول مثل تعداد افرازها هنوز فرمولی ندارند. برنامه های تشخیص هم هنوز خیلی کند هستند. دلیل استفاده از اعداد اول در رمز نگاری هم دقیقا همین کند بودن تشخیصه که البته داره با سیستمها کوانتومی زیر سوال برده می شه جدیدا.

Re: آیا اعداد اول فرمول دارند؟

ارسال شده: سه‌شنبه ۱۳۹۳/۷/۱۵ - ۰۱:۲۹
توسط mmeftahpour
البته تشخیص اینکه یک عدد اول هست یا خیر زمان ریادی نمی برد. (حتی برای اعدادی با 1000 رقم) مشکل وقتی شروع می شود که بخواهیم بدانیم فاکتورهای یک عدد مرکب بزرگ دقیقا چه اعدادی هستند.
اعداد اولی که در رمزنگاری استقاده می شود در کسری از ثانیه تولید می شوند و اگر برای چک کردن اول بودن اعداد ماهها زمان لازم بود؛ بانکها تعطیل می شدند.
رمزها از ضرب دو عدد اول بزرگ ایجاد می شوند. تولید عدد اول و ضرب آنها خیلی آسان و سریع است ولی مسیر معکوس و تجزیه رمز به عاملهای اول به این سادگی نیست.

Re: آیا اعداد اول فرمول دارند؟

ارسال شده: سه‌شنبه ۱۳۹۳/۷/۱۵ - ۱۰:۰۶
توسط You-See
پس یک نگاه دوباره باید به روند تولید کلید اصلی و خصوصی در رمزنگاری بندازید.
تولید اعداد ثانیه ای هست، ولی هرگز چک کردن اول بودنشون سریع نیست. در اصل با داشتن عدد اول شماره یک، و تقسیم بر اون، چک کردن انجام می شه.
تشخیص اول بودن عددی بسیار بسیار زمان بره. بیرون آوردن فاکتور های اون هم همین طور. اگر داستان به همین سادگی بود، نباید برای پیداکردن عدد اول بزرگ جایزه می گذاشتند. در این صورت یک برنامه بصورت رندوم اعداد بزرگ تولید می کرد، و تست می کرد اوله یا نه. به همین سادگی.
اگر برنامه ای دیدید یا می شناسید یا دارید که برای اعداد اول بالای 1000 رقم به زمانی مثلا چند ثانیه بیشتر نیاز ندارد، (بدون استفاده از ابرکامپیوتر، یا محاسبات ابری توزیع شده) لطف کرده به من لینک بدید تا خودم رو آپدیت کنم و برنامه های تا امروزم رو بریزم سطل آشغال. یک سر تعظیم بلند بالا هم تقدیم شما خواهم کرد.

توصیه می کنم این مطلب رو با دقت بخونید:
http://en.wikipedia.org/wiki/Primality_test

و در مورد Order یک الگوریتم یکم تحقیق کنید. به طور مثال برای (O((Log n )^6 (بهترین الگوریتم) ، یک عدد 1000 رقمی می شه 1000 به توان 6 (اگر مبنا رو 10 در نظر بگیریم)، یعنی این که 10 به توان 18 محاسبه در بهترین حالت، تازه منظور از محاسبه، شیفت یا اور یا جمع ساده هم نیست، یک تقسیم کت و کلفته که خودش کلی زمان بره. برای مثال اگر قرار باشه یک میلیون از این محاسبات فقط یک ثانیه طول بکشه، 10 به توان 15 ثانیه زمان خواهد برد. یه چیزی حدود میلیون سال. در نظر بگیریم مثلا یک تریلیون محاسبه فقط در یک ثانیه انجام بشه (!!!)، یک میلیون ثانیه یعنی 11 روز ناقابل زمان خواهد برد.

لطفا دلیل نقض خودتون رو با ذکر منبع، کد، نمونه مثال یا هر چیز قابل استناد دیگه ای ارائه بدید. متشکرم.

Re: آیا اعداد اول فرمول دارند؟

ارسال شده: چهارشنبه ۱۳۹۳/۷/۱۶ - ۲۲:۳۶
توسط خروش
در اینجا شماره ١۰۰۰ رقمی دادم، بی درنگ پاسخ آن را بدست آوردم:

http://primzahlen.zeta24.com/de/online_primzahltest.php

روبروی n = می توانید یک شماره هزاررقمی بدهید، و سپس Start را فشار دهید.

------
http://en.wikipedia.org/wiki/Miller%E2% ... ality_test

Re: آیا اعداد اول فرمول دارند؟

ارسال شده: پنج‌شنبه ۱۳۹۳/۷/۱۷ - ۰۰:۰۲
توسط mmeftahpour
ممنون خروش عزیز
من هم یک سایت مشابه قبلا پیدا کرده بودم ولی متاسفانه نتونستم اونو پیدا کنم. از لینکی که گذاشتین واقعا سپاسگزارم.

Re: آیا اعداد اول فرمول دارند؟

ارسال شده: پنج‌شنبه ۱۳۹۳/۷/۱۷ - ۰۰:۲۲
توسط mmeftahpour
تولید اعداد ثانیه ای هست، ولی هرگز چک کردن اول بودنشون سریع نیست. در اصل با داشتن عدد اول شماره یک، و تقسیم بر اون، چک کردن انجام می شه.
تشخیص اول بودن عددی بسیار بسیار زمان بره. بیرون آوردن فاکتور های اون هم همین طور. اگر داستان به همین سادگی بود، نباید برای پیداکردن عدد اول بزرگ جایزه می گذاشتند. در این صورت یک برنامه بصورت رندوم اعداد بزرگ تولید می کرد، و تست می کرد اوله یا نه. به همین سادگی.


در خصوص اعداد اول بزرگی که براش جایزه گذاشتن باید بگم کلمه "بزرگ" مبهم است. تا چند رقم بزرگ محسوب می شود. بزرگترین عدد اول محاسبه شده 17 میلیون رقمی است.

ابن که من خدمت دوستان گفتم "چک کردن اینکه یک عدد اول است یا نه" برای اعداد تا 1000 رقم هم خیلی سریع است باید اضافه کنم فقط در این فرآیند مشخص می شود عدد اول است یا مرکب. ولی تشخیص اینکه عامل های عدد مرکب ؛ دقیقا چه اعدادی هستند؛ امکان پذیر نمی باشد.
چیزی که در رمزنگاری مورد نیاز است تجزیه کردن رمز است (به عاملهای مشخص) وگرنه مشخص است که همه رمزها مرکبند.
و این تجزیه برای اعداد 200 رقمی هم بقول دوستمان (روح مجرد) از توان کامپیوترهای معمولی خارج است.

Re: آیا اعداد اول فرمول دارند؟

ارسال شده: شنبه ۱۳۹۳/۷/۱۹ - ۱۲:۴۷
توسط You-See
هنوز قانع نشدم،
برنامه تحت وب دارای دیتابیسه و از روشهای توزیع شده ممکنه استفاده کنه.
لطفا سورس کد یا اپ بدید.

Re: آیا اعداد اول فرمول دارند؟

ارسال شده: شنبه ۱۳۹۳/۷/۱۹ - ۱۳:۵۳
توسط خروش
لینک بالا (Miller–Rabin primality test) را دیدید؟

Re: آیا اعداد اول فرمول دارند؟

ارسال شده: یک‌شنبه ۱۳۹۳/۷/۲۰ - ۰۰:۳۹
توسط You-See
به نظر من الگوریتم تشخیص اعداد اول مرسنه نه همه اعداد. درست می گم؟

Re: آیا اعداد اول فرمول دارند؟

ارسال شده: یک‌شنبه ۱۳۹۳/۷/۲۰ - ۰۲:۰۵
توسط MA102
دانشجو هسته ای نوشته شده:یکی دیگه هم هست به فرم : [tex]f(n) = n^2 -n + 41[/tex]

که به ازای n=1,2,3,…,40 اوله، اما به ازای n=41 دیگه درست نیست و فرمول نقص میشه.


یا [tex]f(n) = n^ 2 - 79 n + 1601[/tex] که به ازای همه n ها تا n=79 اعداد اول رو نشن میده اما به ازای n=80 عدد اول نمیده...


همون طور که دیدین هیچ کدوم از فرمولا تمام اعداد اول رو به طور کامل نشون ندادن.


اگه فرمول کاملی هست ،لطفا بگید. smile072

من از اینجور فرمولا خوشم میاد smile084
سایتی هست که ی مجموعه از این نوع فرمولها رُ معرفی کنه.



smile072 smile072 smile072 smile072 smile072 smile072 smile072

Re: آیا اعداد اول فرمول دارند؟

ارسال شده: یک‌شنبه ۱۳۹۳/۷/۲۰ - ۲۳:۲۴
توسط عطر یاس
MA102 نوشته شده:من از اینجور فرمولا خوشم میاد smile084
سایتی هست که ی مجموعه از این نوع فرمولها رُ معرفی کنه.


نمیدونم. ولی این چند تا فرمولی که گذاشتم نمونه کوچیکی از صد ها فرمولی هست که بعضی از اعداد اول رو با محدودیت هایی میتونن نشون بدن. smile072

Re: آیا اعداد اول فرمول دارند؟

ارسال شده: یک‌شنبه ۱۳۹۳/۸/۱۱ - ۰۹:۰۳
توسط رادمهر
به نظر من هیچ فرمولی وجود ندارد.
به علت این که رشد اعداد اول نامنظم است وفرمول با یه نظمی جلو میره.
دانشمند دنبال این هستند که ثابت کنن همچین فرمولی وجود نداره

Re: آیا اعداد اول فرمول دارند؟

ارسال شده: سه‌شنبه ۱۳۹۳/۱۲/۵ - ۱۹:۲۵
توسط Milad74
اگه فرمول داشت حدث گلدباخ و آخرین قضیه ی فرما رو می تونستیم حل کنیم.

Re: آیا اعداد اول فرمول دارند؟

ارسال شده: شنبه ۱۳۹۳/۱۲/۱۶ - ۱۳:۱۷
توسط reza-sad
من یک قاعده شنیدم که می خواستم دوستان هم درباره اون نظر بدهند و آن این که هیچ گاه نمی توانیم برای تمام اعداد اول فرمولی پیدا کنیم. می خواستم بدونم این درسته؟
حتما نظر بدین.

Re: آیا اعداد اول فرمول دارند؟

ارسال شده: سه‌شنبه ۱۳۹۴/۱/۴ - ۱۴:۵۳
توسط مغز متفکر1
یه چیز جالب!!!!
همه ی اعداد اول ضرایب 6 به اضافه یا منهای 1 هستند.(به جز 2و3)
مثلا:41 مساوی 7 ضربدر 6 منهای 1