СПРОСИ ПРОФИ
👍
+1
👎 125

Задача маткрипто олимпиады

Число 201071131 является произведением двух простых чисел p и q , а количество натуральных чисел, меньших заданного числа и взаимно простых с ним, равно 201041064. Найти p,q/
математика обучение     #1   29 ноя 2010 10:24   Увидели: 72 клиента, 5 специалистов   Ответить
👍
+3
👎 3
http://ru.wikipedia.org/wiki/Функция_Эйлера

Поскольку функция Эйлера для заданного числа четная, легко найти её разложение не множители, и отсюда найти p и q.
👍
−1
👎 -1
Извините что вмешиваюсь, но на самом деле трудоемко найти разложение на множители числа 201041064=7*8*9*398891, а число 398891=239*1669 (вручную считать очень долго, а машинный перебор в задаче вряд ли разрешен).
👍
+2
👎 2
Учиться, учиться и еще раз учиться. Раньше МВТУ называли- высшее ремесленное училище.
  #7   29 ноя 2010 23:39   Ответить
👍
−1
👎 -1
Да я в курсе, только Вы это к чему?
👍
−2
👎 -2
Разложение числа на множители здесь вообще не нужно. Зачем Вы это говорили??????Тем более, что множители 8 и 9 не простые числа.
Это задача для школьников , стремящихся поступить в ИКСИ ФСБ России. Для школьников. А Вы себя именуете математиком в компьютерной безопасности.
  #10   30 ноя 2010 00:43   Ответить
👍
−2
👎 -2
Я в курсе, и это был мой ответ Марии Александровне, если я правильно поняла, она предложила разложить на множители.Или нет?Может я не так ее поняла?
👍
+1
👎 1
Мария Александровна квалифицировано увидела , что второе число в условии задачи по определению есть функция Эйлера и для данного конкретного случая n=pq эту функцию Эйлера можно разложить в произведение двух множителей, а именно: (p-1)(q-1).
  #12   30 ноя 2010 09:47   Ответить
👍
−1
👎 -1
Значит я ее неправильно поняла, прошу прощения, я решила что Мария Александровна предложила разложить само число 201041064, почему я и указала на нецелесообразность такого подхода.
👍
0
👎 0
Мне интересно, у Вас на первом курсе на специальности "Информационная безопасность" был предмет "Высшая арифметика". ???Без этого предмета нельзя стать спецом в этой области. Сейчас почти во всех ВУЗах модно иметь такую специальность. При СССР во всей стране с трудом можно было найти сотню ребят, способных учиться по этой специальности.
  #16   30 ноя 2010 18:25   Ответить
👍
0
👎 0
У нас этот предмет назывался просто "Информатика" (не путать с программированием и технологией программирования). И да, мы изучали и функцию Эйлера, и много еще чего. Может Вас еще что-то интересует, спрашивайте, я расскажу :))
👍
−2
👎 -2
Итак, арифметики у Вас не было. А дискретная математика была??? А а абстрактная алгебра была??? Кольца, поля Галуа??? Модульное гаммирование??
  #18   01 дек 2010 00:18   Ответить
👍
0
👎 0
Дискретка была (предмет не кафедральный), доп.главы дискретки были (уже кафедральный предмет), так же как и тервер (не кафедральный) и доп.главы (кафедральный), еще кафедральные были комбинаторика, мат.логика и теория алгоритмов, теория групп, полей, колец(среди этих курсов теоремы арифметики изучаются, но в отдельный предмет не выделяется), группы и поля мы и сейчас изучаем, нам читают курс "Алгебраические системы". Ничего, связанного с криптографией и шифрованием (а модульное гаммирование я так понимаю уже близко к ним) нам пока еще не читали, это еще только впереди.
👍
−1
👎 -1
Все, последний вопрос, мне просто любопытно, поскольку мне приходится сталкиваться с подготовкой специалистов в этой области в разных ВУЗах. Я сейчас хочу дать Вам маленькую арифметическую задачу, связанную сj всей этой тематикой. Не потому, чтобы именно Вас проверить. а вообще. Ибо только задачи выявляют понимание
Вычислить 3/7+1/3 (mod 17).
  #20   01 дек 2010 01:14   Ответить
👍
+1
👎 1
Рассмотрим 3/7. Деление на 7 эквивалентно умножению на обратный элемент семи в поле Z17.Этот обратный элемент = 5(т.к. 5*7 = 35 = 1mod17).Значит 3/7 = 3*5=15.Далее 1/3, ищем обратный элемент для 3, это 6 (т.к. 3*6 =18 = 1mod17). Значит 1/3 = 1*6 = 6.И окончательно (15+6)mod17 = 4mod17.
👍
+1
👎 1
Сложно Вас учили. Гораздо проще: решить сравнение 21x=16(mod17), отсюда х=4(mod17). 21 и 16 берутся от обычного сложения исходных дробей.
  #23   01 дек 2010 10:05   Ответить
👍
−1
👎 -1
Тяжело в учении, легко в бою. А уравнения вида ax=b mod c нас учили решать в этом семестре.
👍
0
👎 0
Марина, тогда Вам надо обратить внимание на новую криптозадачу(олимпиадную для школьников), представленную опять же Смолиным Игорем/
  #26   01 дек 2010 14:35   Ответить
👍
+1
👎 1
Чтобы найти два числа, мне надо два уравнения. Пока мне не очень ясно , какие это уравнения, хотя одно из условия задачи вытекает. Как из функции Эйлера сделать уравнение?
  #3   29 ноя 2010 14:10   Ответить
👍
0
👎 0
p+q = p*q — (p-1)*(q-1) + 1 = 201071131 — 201041064 + 1 = 30068
Таким образом 'p' является корнем ур-я p^2 — 30068p + 201071131 = 0, корни которого
15064+-4995.
👍
+1
👎 1
Функция Эйлера в данном случае есть (q-1)(p-1) и потому эти числа являются корнями системы pq= 201071131
(p-1)(q-1)=201071
Данная система конечно же сводится к решению квадратного уравнения
х^2 -30068х+201071131=0. Только корни этого уравнения p=10039 и q=20029
  #6   29 ноя 2010 23:30   Ответить
👍
−1
👎 -1
Я так понимаю, Марк Михайлович имел в виду корни 15064+4995=20029 и 15064-4995=10039, просто записал их в одну строчку через +/- ...
👍
−1
👎 -1
Ошибка есть ошибка. Доказывайте на ЕГЭ, что Вы описались. Я,например, половину времени с учениками трачу на воспитание внимательности. Приходится применять специально ( не мною) разработанные методы. Ведь и родителям результат в виде баллов надо.
  #13   30 ноя 2010 09:54   Ответить
👍
−1
👎 -1
Я все свои ЕГЭ уже давно сдала, а описка находится в середине задачи и не приводит к неправильному ответу, уж если речь зашла о ЕГЭ.
👍
+1
👎 1
Спасибо всем. Я узнал много интересного. Моя задача действительно задача 20-ой Межрегиональной олимпиады школьников по математике и криптографии (1-ый тур). Особенно спасибо за функцию Эйлера, её разложение для моего случая. Мои преподаватели доказывали это разложение сами без функции Эйлера.
Мне также оказалась очень полезна задача: 3/7+1/3 (mod 17). Поэтому спасибо Круглову и Якушевой. Мне никто подобную задачу не мог объяснить.
  #22   01 дек 2010 09:36   Ответить
👍
+1
👎 1
Совет Игорю. Почитайте книгу Г. Дэвенпорт "Высшая арифметика"
  #24   01 дек 2010 10:07   Ответить

Задайте свой вопрос по математике
профессионалам

Сейчас онлайн 75 репетиторов по математике
Получите ответ профи быстро и бесплатно

Другие вопросы на эту тему:

👍
0
👎 08

Найти собственные значения и собственные векторы линейного преобразования, заданного матрицей А   8 ответов

А=1 -3 -3
-2 -6 13, составим характеристическое уравнение1-л -3 -3
-1 4 8 -2 -6-л 13=0
-1 4 8-л
раскроем полученный определитель по правилу треугольника, приведем подобные, получим характеристический многочлен
–л^ 3+3л^ 2+107л-67=0
раскладываем полученный…
  12 ноя 2018 22:18  
👍
0
👎 04

Мощность множеств   4 ответа

Помогите разобраться с доказательством. Не могу наглядно представить взаимно однозначное соответствие описанное в доказательстве?

Теорема: Множество всех возрастающих последовательностей натуральных чисел имеет мощность континуума.
Доказательство:
Предположим, что последовательность {Kn} является возрастающей последовательностью натуральных чисел. Это означает, что K1<K2<...<Kn<...
Мы можем поставить этой последовательности…
  04 май 2017 19:35  
👍
0
👎 09

Найти число   9 ответов

Известно, что число 23909951 равно остатку от деления на 59214403 некоторого
числа x , возведенного в куб. Числа x и 59214403 имеют общий делитель, отличный от 1, а число 59214403 является произведением двух простых чисел. Найдите хотя бы одно такое число x .
  20 окт 2015 13:05  
👍
+1
👎 137

Порядок элемента группы   37 ответов

Как найти именно наименьший порядок элемента группы. Как найти все элементы заданного порядка в группе.
В типовом домашнем задании эти задачи есть, а лекции только по линейной алгебре. Лектор говорит, чтобы общую алгебру мы изучали самостоятельно. Наверное, сам не знает. Вот такое обучение в ВУЗе.
  14 окт 2013 15:57  
👍
0
👎 00

Помогите, пожалуйста, с заданиями по геометрии   0 ответов

1. Пользуясь инвариантами, привести к простейшему виду уравнение кривой x^2 — 2xy + y ^2 − x − 2y + 3 = 0
2. Пользуясь перенесением начала координат, упростить уравнение кривой 7x^2 + 4xy + 4y ^2 − 40x − 32y + 5 = 0
3.На прямой 4х+3у-12=0 найти точку, полярно сопряженную с началом координат относительно кривой 9х^2+24xy+16y^2-40x+30y=0
4.Исследовать кривую, предварительно повернув оси ординат так, чтобы преобразованное уравнение не содержало члена с произведением координат х^2+4xy+y^2-3=0
👍
+2
👎 218

С6. Составное число.   18 ответов

Натуральное число представимо в виде произведения различных простых множителей. Сумма всех его делителей равна 384. Количество чисел, меньших данного числа и взаимно простых с ним равно 120. Найти это число.
ASK.PROFI.RU © 2020-2024