555_Innovatsii_inauchno-tekhnicheskoe_tvorchestvo_molodezhi2014_

Иерархичность базиса приводит к блочной структуре конечноэлементых матриц, что дает возможность использовать специальные многоуровневые решатели СЛАУ [4].

После конечноэлементной дискретизации, задача (4) принимает вид обобщенной проблемы на собственные значения:

(5)

Минимальные собственные значения задачи (5) соответствуют

При реализации метода Ланцоша в конечной арифметике, из-за накопления погрешности, неизбежно появляется потеря ортогональности [5] векторов . Чтобы этого избежать, после шага 5 проводят процедуру реортогонализации. В работе используется метод частичной реортогонализации [5]. Суть метода состоит в том, что очередной вектор

ортогонализуется относительно не всей системы векторов, а лишь некоторой её части, выбор которой основывается на априорных оценках.

331

Впоследнее время всю большую популярность приобретают вычисления общего назначения на графических процессорах (GPU). За счет использования высокой степени параллелизма графических процессоров, во многих вычислительных задачах удается получить более высокую производительность, по сравнению с центральными процессорами (CPU)[6].

Вработе рассматривается реализация решения обобщенной спектральной задачи на графических процессорах. Реализуются эффективные разреженные матрично-векторные произведения, лежащие в основе численного моделирования векторным методом конечных элементов.

Литература:

1.Buck J.A. Fundamentals of optical fibers: A Wiley-Interscience Publication, 1995.

– 264 P.

2.Баландин М.Ю., Шурина Э.П. Векторный метод конечных элементов: Учеб.пособие. – Новосибирск: Изд-во НГТУ, 2001. – 69с.

3.Jin J. The Finite element method in electromagnetics: A Wiley-Interscience Publication, 2002. - 780 P.

4.Nechaev O., Shurina E., Botchev M. Multilevel iterative solvers for the edge finite element solution of the 3D Maxwell equation // Computers and Mathematics with Applications. № 10 – 2008, 16 p.

5.Simon H.D. The Lanczos Algorithm With Partial Reorthogonalization: Mathematics of computation vol. 42, no. 185, january 1984, p. 115 – 142

6.Боресков А.В., Харламов А.А. Основы работы с технологией CUDA – Москва: Изд-во ДМК Пресс, 2010 – 232с.

РАЗРАБОТКА И РЕАЛИЗАЦИЯ АЛГОРИТМОВ 2D-ИНВЕРСИИ ДАННЫХ ЭЛЕКТРОМАГНИТНОГО КАРОТАЖА С ПОИСКОМ ВЕРТИКАЛЬНЫХ ГРАНИЦ ОБЪЕКТОВ

Кошкина Ю.И. НГТУ, Новосибирск

e-mail: koshkina_yui@mail.ru, тел. (383)346-27-76

Научный руководитель - Персова М.Г., профессор НГТУ

Одним из распространенных подходов к выполнению 2D-инверсии данных является подход, основанный на поиске значений удельной электрической проводимости (УЭП) в ячейках сетки, наложенной на изучаемую среду [1]. Однако такой подход, в случае если границы ячеистой структуры не совпадают с реальными границами объектов, не позволяет подобрать модель адекватную истинной. Поэтому в ходе данной работы были разработаны и реализованы алгоритмы 2D-инверсии данных электромагнитного каротажа с поиском границ объектов. Здесь представлены результаты апробации полученного программноматематического обеспечения, позволяющего проводить поиск помимо значений УЭП в ячейках, еще и положений вертикальных границ ячеистой структуры.

332

Опишем математический аппарат, используемый для интерпретации данных. Искомые параметры будут определяться на основании минимизации функционала:

где N – количество точек измерений, M количество искомых параметров, Vi(b)

–теоретические данные, полученные в i-й точке измерения, Vi –практические данные, m коэффициент регуляризации, b0 – вектор начального распределения

значений искомых параметров, b – направление вектора b0, b – вектор некоторых фиксированных параметров, определяющих регуляризирующую добавку.

С учетом линеаризации по методу Ньютона отклонения практических и расчетных данных переписывается функционал Ф(b). Затем от полученного выражения берется производная по b, и полученный результат приравнивается к нулю. Таким образом, обратная задача сводится к решению системы линейных алгебраических уравнений

Анализ влияния положения вертикальных границ ячеистой структуры на результат инверсии данных проводился для модели среды, представленной на рисунке 1.

Для измерения разности фаз были использованы три зонда. Геометрические размеры этих зондов и величины их рабочих частот приведены в работе [2].

Первые исследования проводились при условии, что границы ячеек, на которые разбивалась среда, совпадали с физическими границами объектов. Результаты таких исследований показали, что значения удельной электрической проводимости были подобраны достаточно адекватно реальной модели (графики теоретических и практических данных почти совпали). Значение функционала невязки при этом уменьшилось от значения 3.89 103 (для начального распределения) до значения 1.29 10-9.

333

Сдвиг вертикальных границ ячеистой структуры оказал значительное влияние на результат 2D-инверсии данных (рисунок 2). Значение функционала невязки при этом уменьшается от значения 3.89 103 до значения 3.36 ·10-1.

На рисунках 2 и 3 показаны: (а) – графики разности фаз; (б) – распределение значений УЭП; (в) – графики значений УЭП. Цифрами 1-3 на графиках разности фаз обозначены данные, полученные приемниками 1-3 зонда соответственно. Пунктирными линиями обозначены истинные значения параметров.

3

2

1

Рисунок 2 - Результаты 2D-инверсии данных со сдвигом вертикальных границ ячеек

Дробление же ячеистой структуры приводит к "пестрой" картине распределений УЭП по ячейкам и не позволяет выделить слои и объекты, соответствующие реальной модели.

Таким образом, из полученных результатов можно сделать вывод, что помимо поиска распределения значений УЭП по ячейкам необходимо проводить поиск r-координаты положения вертикальных границ ячеек. Использование такого подхода позволяет получить близкие к реальным положения вертикальных границ и значения УЭП в ячейках при условии, что границы ячеек по оси OZ совпадают с границами реальной среды (Рис. 3).

334

3

2

1

Рисунок 3 - Результаты 2D-инверсии данных с поиском положений вертикальных границ ячеистой структуры

В случае, когда границы сеточной структуры сдвинуты по оси OZ, для получения результата адекватного истинной модели необходимо либо двигать горизонтальные границы ячеистой структуры в местах с наибольшим отклонением расчетных данных от практических, либо искать z-координаты границ с помощью 2D-инверсии, используя в качестве искомых параметров помимо значений УЭП и положений вертикальных границ еще и положения горизонтальных границ.

Литература:

1.Жданов М.С. Теория обратных задач и регуляризации в геофизике. – М.:

Научный мир, 2007. – 712 с.;

2.Аппаратура высокочастотного индукционного каротажного изопараметрического зондирования. Руководство по эксплуатации. ЛУЧ 6.00.00.00 РЭ. // – Новосибирск: ЗАО Научно-производственное предприятие геофизической аппаратуры ЛУЧ, 2005. – 16 с.

335

АПЕРИОДИЧЕСКИЙ ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ, ОСНОВАННЫЙ НА РЕШЕНИИ

УРАВНЕНИЙ В P-АДИЧЕСКИХ ЧИСЛАХ

Кузьменок А.Ю., Ельчугин М.О. НГТУ, лаборатория НГУ-Parallels, Новосибирск e-mail: Aleknock@yandex.ru, тел. 8-952-904-69-27

Научный руководитель – Кренделев С.Ф., доцент НГТУ

Большинство криптографических систем нашего времени требует использования генераторов псевдослучайных чисел. Причем, нередко выбор того или иного генератора оказывается наиболее важным, так как от надежности генератора напрямую зависит качество приложения. Серьезным недостатком подавляющего числа существующих генераторов является наличие слишком коротких периодов и неприемлемые статистические свойства генерируемых последовательностей.

Идея использования p-адических чисел [1, 2] для генерации псевдослучайных чисел не является новой [3, 4, 5]. Так, например, A.Klapper и M.Goresky для построения генераторов битовых последовательностей

использовали 2-адическое представление рационального числа b , где a и

a

bвзаимно простые числа и a нечетное [3]. Легко заметить, что на самом деле идет речь о представлении решения уравнения с целочисленными

последовательность псевдослучайных чисел. Очевидно, что генерируемая последовательность имеет период. С целью увеличения периода данный подход можно модифицировать, если использовать идеи из работы J.D. Dixon [6], и

целочисленный вектор. Однако в большинстве случаев использование этого способа также не дает приемлемой длины периода.

В данной работе рассмотрен вариант p-адического представления иррациональных или комплексных чисел, которые являются решениями алгебраического уравнения f x 0 , где – многочлен степени m 2 с целыми коэффициентами. Очевидно, что в этом случае представление этих чисел в виде не является периодическим и последовательность коэффициентов разложения {ti} может быть использована в качестве последовательности псевдослучайных чисел.

Несложно заметить, что для того чтобы найти ti,i 0,1,2,..., необходимо решить последовательно сравнения

n

f xn 0 mod pn 1 , xn ti pi,n 0,1,2,...

i 0

336

Для существования решений этих сравнений необходимо, чтобы существовало решение сравнения f x0 0 mod p [7]. Поскольку решение данного сравнения в общем случае не единственно, то выбор решения также является параметром генератора и определяет вид результирующей последовательности.

Для того чтобы генератор псевдослучайных чисел возможно было использовать в криптосистемах необходимо, чтобы статистические свойства генерируемых им последовательностей полностью соответствовали свойствам случайных последовательностей. Вывод о том, насколько последовательность случайна, позволяют сделать стандартные наборы статистических тестов, объединенные единой методикой расчета необходимых показателей эффективности генератора.

Для исследования статистических свойств данного генератора использовался один из наиболее известных в настоящее время наборов стандартных статистических тестов NIST STS [8], разработанный национальным институтом стандартов и технологий США. Выбор данного пакета обусловлен тем, что он имеет большую криптологическую направленность, которая достигается путем введения в пакет таких тестов, как проверка линейной сложности и универсального теста Маурера. В результате проведенного тестирования можно сделать вывод о том, что генератор успешно прошел все 15 тестов NIST и удовлетворяет свойствам случайных последовательностей.

Для проверки статистических свойств генератора были взяты последовательности по модулю 2 длинной один миллион бит. В качестве ключей использовались полиномы второй степени, дискриминант которых не является полным квадратом или отрицателен и производная которых не равна нулю по модулю 2. Тестирование проводилось при уровне значимости 0.01.

Исследования показали, что для всех выборок значения вероятностей прохождения i-го теста равномерно распределены, а доля последовательностей, успешно прошедших тест, попадает в доверительный интервал. Более того, сводные графики проверки первого условия показывают, что доли последовательностей, прошедших тест, лежат преимущественно в центре доверительного интервала и при увеличении количества последовательностей в выборке стремятся к идеальному значению равному 0.99.

Таким образом, в результате проведенных исследований можно сделать вывод о том, что генератор прошел все статистические тесты пакета NIST.

Очевидным преимуществом представленного генератора является отсутствие периода и хорошие статистические свойства. Немаловажное значение имеет и простота выбора ключа для генератора: необходимо, выбирать те полиномы, у которых нет рациональных корней и производная которых не равна нулю по выбранному модулю. Однако стоит отметить, что с увеличением длины генерируемой последовательности значительно уменьшается скорость генерации каждого последующего числа. Решением этой проблемы может являться смена первоначального полинома по некоторому правилу после определенного количества итераций.

337

Литература:

1.N. Koblitz. P-Adic Numbers, p-Adic Analysis, and Zeta Functions. Graduate Texts in Mathematics Vol. 58, Springer-Verlag, New York, 1984

2.H.D. Ebbinghaus et al., Numbers, Graduate Texts in Mathemattics vol. 123, Springer Verlag, N.Y., 1990.

3.A.Klapper and M. Goresky. Feedback Shift Registers, 2-Adic Span, and Combiners with Memory, Journal of Cryptology (1997) 10: 111-147

4.M. Goresky, A. Klapper: 2-adic shift registers, Proceedings, Fast Software Encryption LNCS, vol. 809, Springer Verlag, 1994: с 174-178.

5.M. Goresky, A. Klapper: Feedback Registers Based on Rami_ed Extensions of the 2-Adic Numbers (Extended Abstract). EUROCRYPT 1994: 215-222.

6.Dixon J. D. Exact solution of linear equations using P-adic expansions Numer. Math., 40, 1982, P. 137-141.

7.Основы теории чисел. И.М. Виноградов. Москва. 1952г. с. 61-65

8.Rukhin A. and others A Statistical Test Suite for Random and Pseudorandom Number Genera-tors for Cryptographic Applications. NIST Special Publication 800-22 Revision 1a April 2010.

ВИЗУАЛИЗАЦИЯ РАБОТЫ АЛГОРИТМОВ ХЭШИРОВАНИЯ

Курлаев С.А., Бармина А.В., Шубина А.В. НГТУ, Новосибирск

e-mail: kurlaevwork@ngs.ru

Научный руководитель - Курлаев С.А., ассистент НГТУ

Всовременном мире ни один программный продукт не обходится без применения криптографических алгоритмов, многие из которых, в свою очередь, используют алгоритмы хэширования.

Такие алгоритмы являются достаточно сложными для понимания, так как имеют определённые сложности реализации, связанные, в основном, с тем, что приходится оперировать большими числами (32–64 бита), что делает проблематичным просчёт алгоритмов вручную, и в процессе отладки практически невозможно проследить все изменения, произошедшие с исходным сообщением до получения его хэш-значения. В связи с этим возникают проблемы отладки приложения для тех, кто пытается реализовать эти алгоритмы. Конечно, существует множество приложений, позволяющих для любого сообщения вычислить его хэш. Но, тем не менее, нет таких, которые могли бы показать промежуточный результат на каждом этапе выполнения алгоритма и наглядно продемонстрировать, каким образом он был получен.

Вучебных курсах, связанных с криптографией, возникает необходимость подробного представления таких алгоритмов.

С учётом этого, была поставлена цель данной работы – разработать программное обеспечение, соответствующее следующим требованиям:

338

программное обеспечение должно наглядно демонстрировать суть всех преобразований, использующихся в алгоритмах хэширования

SHA и MD5;

программное обеспечение должно облегчить понимание принципов работы этих алгоритмов;

программное обеспечение должно позволить отследить в процессе отладки, где и какие ошибки были допущены при разработке пользовательского приложения, реализующего данные алгоритмы хэширования. В частности, в процессе написания студентами

лабораторных работ по дисциплинам, связанным с информационной безопасностью и криптографией.

Для того чтобы выполнить вышеописанные требования к программному обеспечению, были проанализированы алгоритмы хэширования SHA и MD5, проработан интерфейс взаимодействия с пользователем с учётом возможности выбора алгоритма и задания входных данных, к которым в последствии будет применяться тот или иной алгоритм, с последующим подробным отображением всех этапов и промежуточных результатов. Так же было проработано визуальное представление алгоритмов, в том числе всех шагов, действия на которых требуют пояснений и наглядного отображения.

Учитывая специфику данной работы, программное обеспечение, удовлетворяющее указанным требованиям, удобно реализовать в виде интерактивной анимации с использованием технологии Flash. Это обусловлено следующими причинами:

Flash-приложение позволяет достаточно просто реализовать, наглядно и красиво отобразить каждый шаг алгоритма.

Flash-приложение позволяет реализовать не просто анимированное изображение или слайд-шоу, а полноценное приложение, позволяющее осуществлять интерактивное взаимодействие с пользователем, в том числе задавать исходные данные для рассматриваемых алгоритмов.

Flash-приложение является кроссплатформенным и кроссбраузерным

(при наличии соответствующих плагинов к браузерам).

Созданное однажды Flash-приложение можно легко интегрировать в вебстраницу либо в десктопное приложение.

Технология Flash является распространённой, следовательно, на компьютерах конечных пользователей обычно уже есть установленное программное обеспечение, необходимое для запуска Flash-приложений.

339

РАЗРАБОТКА ВЕБ-ПОРТАЛА ДЛЯ КОМПАНИИ, ЗАНИМАЮЩЕЙСЯ ПРОВЕДЕНИЕМ ЭЛЕКТРОННЫХ ПЛАТЕЖЕЙ

Курлаев С.А., Грунев В.В. НГТУ, Новосибирск e-mail: kurlaevwork@ngs.ru

Научный руководитель - Курлаев С.А., ассистент НГТУ

Для организации, занимающейся приемом и проведением платежей посредством терминалов самообслуживания, необходимо разработать вебпортал, который бы предоставлял функционал, необходимый для администрирования имеющейся на данный момент системы по проведению платежей.

Пользователи разрабатываемого портала – это владельцы системы и их агенты (лица, проводящие платежи и получающие за это вознаграждение). Пользователи получают доступ к системе с помощью сертификатов x.509.

Портал должен предоставлять пользователям следующие услуги:

мониторинг состояния и поведения терминалов (работоспособность, количество денег в купюроприемнике, время последнего обращения на сервер и т.д.);

настройка терминалов (пользовательский интерфейс, комиссия и т.д.);

заведение в системе провайдеров услуг, редактирование их настроек (доступно только владельцам системы);

просмотр информации по платежам. Возможность поиска и перепроведения;

просмотр актов об оказанных услугах по договорам с агентами;

статистика по терминалам, провайдерам, счетам агентов;

настройки агентов (задание реквизитов, настройка sms-оповещений, установка сертификатов и т.д.);

оперативный контроль: информация, требующая постоянного

внимания, состояния счетов агентов, состояния счетов у операторов (организаций, напрямую сотрудничающих с провайдерами и проводящих платежи), платежи, требующие вмешательства, проблемные терминалы, сертификаты с истекающим сроком подлинности.

Для реализации портала решено использовать технологию ASP.NET Web Forms в связи с наличием таких преимуществ, как:

наличие огромного количества серверных элементов управления;

концепция событийного программирования;

более быстрая и простая разработка, благодаря событиям, ViewState и серверным элементам управления;

более удобная разработка бизнес-приложений, работающих с большими объемами данных и зависящих от данных.

340