|
F (x) va h (z, v, w) funksiyalari ikkita funktsiyaga aylanishi mumkin. H (z, v, w) funktsiyasida dastlabki ikki argument uzun raqamlar, uchinchisi esa bitwise. F va h funktsiyalari O1 va O2 ob'ektlariga ma'lum va ular ushbu funktsiyalarning qadriyatlarini argumentlarning berilgan qiymatlari uchun tez hisoblash uchun algoritmlarni bilishadi, lekin ular bu vazifalarni tezda qanday qilib tezda o'zgartirishni bilishmaydi, tenglamalarni echish.
Quyidagilar quyida keltirilgan bosqichlardan iborat.
O2 ob'ekti tasodifiy ravishda katta intervaldan [0, q-1] x sonini tanlaydi.
Y = f (x) funksiyasini qaytaradi.
2. O2 obyekti y ning raqamini O1 ob'ektiga yo'naltiradi. O1 obyekti x sonini tiklay olmaydi.
3. O1 ob'ekti katta oraliqdagi [0, q-1] orasidagi raqamni tasodifiy tanlaydi. O1 obyekti tasodifiy bitni w ni tanlaydi. Bu harakatlar 1-band bilan bir vaqtning o'zida amalga oshirilishi mumkin.
4. O1 ob'ekti s = h (z, y, w) ni hisoblaydi. Bu erda z zonasi "niqob" va "y" - ob'ekt O1 ob'ektlarining xatti-harakatlarining to'g'riligiga O2 ob'ektini "tekshirish" uchun kerak.
5. O1 ob'ekti s ni O2 ob'ektiga yuboradi. Bit w, O2 obyektiga yuboriladi, lekin u sonlar ichida "yashirin". O2 ob’yekti bu bitni saqlab qo'lolmaydi. O2 obyekti z raqamini tiklay olmaydi.
6. O2 obyekti tasodifiy bitni tanlaydi.
7. O2 obyekti O1 ob'ektiga bir oz yuboradi. Yuk tashish uchun ochiq.
8. O1 ob'ekti z va bit w ni O2 ob'ektiga yuboradi. Yuk tashish uchun ochiq. O1 obyekti allaqachon lotereya lotereyalari natijalarini aniqlab berishi mumkin: c + w (mod 2).
9. O2 ob'ekti t = h (z, y, w) ni hisoblaydi. Bu erda z va w faqat O1 dan olinadi va y 1-bandda hisoblab chiqilgan.
10. O2 ob’yekti avval O1 ob'ektidan olingan t va s ni solishtiradi.
11. Agar t = s bo'lsa, u holda O2 obyekti lotereya lotlarining natijasini hisoblaydi:
c + w (mod 2).
F va h funktsiyalari har xil bo'lishi mumkin. Xususan, quyidagi funktsiyalar qo'llaniladi:
f(x) = gx (mod p) и h(z, v, w) = vwgz (mod p).
Bu erda x, w, z ning "yashirin" qiymatlari vakolat doirasiga kiradi va ularni topish uchun aniq qidiruv tizimidan ancha yaxshi bo'lgan algoritm aniq bo'lgan logaritma muammosini hal qilish talab qilinadi.
P, q, g sobit ikkala ob'ektga ma'lum bo'lishi kerak. P soni uzoq boshlang'ich raqam. Q raqami ham p-1 sonining bo'lagi bo'lgan uzoq boshlang'ich raqamdir. 1 gacha bo'lmagan g g p g g = 1 (mod p) holatiga mos keladi.
Yig'ilgan muammolarni hal qiladigan tarqalgan algoritmlar. Tarqatilayotgan algoritmlarni rivojlantirishning yo'nalishlaridan biri yuqori samarali hisoblash hisoblanadi. Bu holda taqsimlangan kompyuter tizimi bir vazifani hal qilishda kuchli hisob-kitob qilish vositasi sifatida ishlatiladi. Mashhur bir misol, DES shifrlash algoritmi tomonidan yaratilgan shifrlarni "buzish" muammosi. Agar shifrlash tugmasi ma'lum bo'lsa, matnning parolini o'zgartirish qiyinlashtirilmaydi. Agar kalit ma'lum bo'lmasa, unda parol hal qilishni to'liq qidirish orqali sinab ko'rish mumkin. Biroq, to'liq qidirish usuli juda tez, hatto eng tezkor protsessorli kompyuterlar uchun ham talab qiladi.
Muammoni echish juda protsessorli kompyuter yordamida tezlashtirilishi mumkin. Bunday holda, hisoblar parallel holga keltiriladi, ya'ni. barcha protsessorlar bir vaqtning o'zida bir xil yoki turli xil buyruqlar bajarib, muammoni hal qilishda ishtirok etishadi. Qanday parallellashtirish amalga oshirilishi juda protsessorli kompyuterning arxitekturasiga bog'liq. Ideal vaziyatda n tarkibida n protsessorlar mavjud bo'lsa, hisoblashlarning tezlashishi n vaqtga yaqin qiymatga ega bo'lishi mumkin. Aslida, algoritmlar to'liq parallel holga kelmagan, ayrim protsessorlar muayyan vaqt oralig'ida bo'sh bo'lishi mumkin, va ishlash n vaqtdan kamroq vaqt bilan ortadi.
Zamonaviy multiprocessor mashinalari o'nlab va yuzlab protsessorlar, minglab protsessorlarga ega. Lekin bunday noyob mashinalar juda qimmat, maxsus superkompyuter markazlarida yoki harbiy tashkilotlarda o'rnatiladi va odatdagi foydalanuvchilar uchun doimo mavjud emas. Shu bilan bir qatorda, global aloqa tarmoqlari bilan bog'langan va shaxslar va turli tashkilotlarga tegishli alohida kompyuterlardan foydalanish. Kompyuterlar nisbatan kam ishlashga ega bo'lishi mumkin, biroq tarmoqdagi bir necha o'nlab yoki yuz minglab kompyuterlarning bitta vazifani hal qilish uchun bir xil superkompyuterning ta'sirini yaratadi, lekin ehtimol yanada kuchli.
Yuqorida keltirilgan parolni hal qilish uchun ishlatiladigan bu tarqalgan kompyuter tizimi. Bu "qattiq" tizim emas edi - kompyuterlar ixtiyoriy ravishda ishlatilgan, istalgan vaqtda har qanday kompyuter tizimdan chiqishi mumkin. Biroq, yangi kompyuterlar kabi mavjud bo'lganlarga qo'shilish mumkin. Kompleks muammolarni hal qilish uchun global kompyuterlar tarmog'idan foydalanish g'oyasi va mos keluvchi texnologiyaga "Grid" nomi berildi.
Agar veb-global axborot resurslariga kirish imkoni bo'lsa, Grid global hisoblash (qayta ishlash) manbalariga kirishni ta'minlashi kerak. Griddan foydalanishning asosiy loyihalari hozirgi vaqtda elementar zarracha fizikasida eksperimental ma'lumotlarning katta soni (terabaytlar, pentabaytlar), astronomiyada kuzatuvlar, biologiyada inson genomining dekodlanishi bilan bog'liq.
Do'stlaringiz bilan baham: |
