Алгоритм датчика случайных чисел

Тесты — Упрощенная генерация случайных чисел

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

В этой статье я покажу, как генерировать случайные числа с помощью четырех разных алгоритмов: алгоритма Лемера (Lehmer), линейного конгруэнтного алгоритма ( linear congruential algorithm), алгоритма Вичмана-Хилла (Wichmann-Hill) и алгоритма Фибоначчи с запаздываниями (lagged Fibonacci algorithm).

Но зачем обременять себя созданием собственного генератора случайных чисел (random number generator, RNG), когда в Microsoft .NET Framework уже есть эффективный и простой в использовании класс Random? Существует два сценария, где вам может понадобиться создать свой RNG. Во-первых, в разные языки программирования встроены разные алгоритмы генерации случайных чисел, а значит, если вы пишете код, который будет переноситься на несколько языков, можно создать собственный RNG, чтобы реализовать его во всех нужных вам языках. Во-вторых, некоторые языки, в частности R, имеют лишь глобальный RNG, поэтому, если вы захотите создать несколько генераторов, вам придется писать свой RNG.

Хороший способ получить представление о том, куда я клоню в этой статье, — взглянуть на демонстрационную программу на рис. 1. Демонстрационная программа начинает с создания очень простого RNGЮ используя алгоритм Лемера. Затем с помощью RNG генерируется 1000 случайных целых чисел между 0 и 9 включительно. За кулисами записываются счетчики для каждого из сгенерированных целых чисел, которые потом отображаются на экране. Этот процесс повторяется для линейного конгруэнтного алгоритма, алгоритма Вичмана-Хилла и алгоритм Фибоначчи с запаздываниями.

Рис. 1. Демонстрация упрощенной генерации случайных чисел

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

Алгоритм Лемера

Самый простой приемлемый метод генерации случайных чисел — алгоритм Лемера. (Для простоты я использую термин «генерация случайных чисел» вместо более точного термина «генерация псевдослучайных чисел».) Выраженный в символьном виде, алгоритм Лемера представляет собой следующее:

На словах это звучит так: «новое случайное число является старым случайным числом, умножаемым на константу a, после чего над результатом выполняется операция по модулю константы m». Например, предположим, что в некий момент текущее случайное число равно 104, a = 3 и m = 100. Тогда новое случайное число будет равно 3 * 104 mod 100 = 312 mod 100 = 12. Вроде бы просто, но в реализации этого алгоритма много хитроумных деталей.

Чтобы создать демонстрационную программу, я запустил Visual Studio, выбрал шаблон C# Console Application и назвал проект RandomNumbers. В этой программе нет значимых зависимостей от .NET Framework, поэтому подойдет любая версия Visual Studio.

После загрузки кода шаблона в окно редактора я переименовал в окне Solution Explorer файл Program.cs в более описательный RandomNumbersProgram.cs, и Visual Studio автоматически переименовала класс Program за меня. В начале кода я удалил все лишние выражения using, оставив только ссылки на пространства имен верхнего уровня System и Collections.Generic.

Затем я добавил класс с именем LehmerRng для реализации RNG-алгоритма Лемера. Код показан на рис. 2. Версия алгоритма Лемера за 1988 год использует a = 16807 и m = 2147483647 (которое является int.MaxValue). Позднее, в 1993 году Лемер предложил другую версию, где a = 48271 как чуть более качественную альтернативу. Эти значения берутся из математической теории. Демонстрационный код основан на знаменитой статье С. К. Парка (S. K. Park) и К. У. Миллера (K. W. Miller) «Random Number Generators: Good Ones Are Hard to Find».

Рис. 2. Реализация алгоритма Лемера

Проблема реализации в том, чтобы предотвращать арифметическое переполнение. Алгоритм Лемера использует ловкий алгебраический трюк. Значение q является результатом m / a (целочисленное деление), а значение r равно m % a (m по модулю a).

При инициализации RNG Лемера начальным (зародышевым) значением можно использовать любое целое число в диапазоне [1, int.MaxValue – 1]. Многие RNG имеют конструктор без параметров, который получает системные дату и время, преобразует их в целое число и использует в качестве начального значения.

RNG Лемера вызывается в методе Main демонстрационной программы:

Каждый вызов метода Next возвращает значение в диапазоне [0.0, 1.0) — больше или равно 0.0 и строго меньше 1.0. Шаблон (int)(hi – lo) * Next + lo) будет возвращать целое число в диапазоне [lo, hi–1].

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

Алгоритм Вичмана-Хилла

Этот алгоритм датируется 1982 годом. Идея Вичмана-Хилла заключается в генерации трех предварительных результатов и последующего их объединения в один финальный результат. Код, реализующий алгоритм Вичмана-Хилла, представлен на рис. 3. Демонстрационный код основан на статье Б. А. Вичмана (B. A. Wichmann) и А. Д. Хилла (I. D. Hill) «Algorithm AS 183: An Efficient and Portable Pseudo-Random Number Generator».

Рис. 3. Реализация алгоритма Вичмана-Хилла

Поскольку алгоритм Вичмана-Хилла использует три разных генерирующих уравнения, он требует трех начальных значений. В этом алгоритме три m-значения равны 30269, 30307 и 30323, поэтому вам понадобятся три начальных значения в диапазоне [1, 30000]. Вы могли бы написать конструктор, принимающий эти три значения, но тогда вы получили бы несколько раздражающий программный интерфейс. В демонстрации применяется параметр с одним начальным значением, генерирующим три рабочих зародыша.

Вызов RNG Вичмана-Хилла осуществляется по тому же шаблону, что и других демонстрационных RNG:

Алгоритм Вичмана-Хилла лишь немного труднее в реализации, чем алгоритм Лемера. Преимущество первого над вторым в том, что алгоритм Вичмана-Хилла генерирует более длинную последовательность (более 6 000 000 000 000 значений) до того, как начнет повторяться.

Линейный конгруэнтный алгоритм

Оказывается, и алгоритм Лемера, и алгоритм Вичмана-Хилла можно считать особыми случаями так называемого линейного конгруэнтного алгоритма (linear congruential, LC). Выраженный в виде уравнения, LC выглядит так:

Это точно соответствует алгоритму Лемера с добавлением дополнительной константы c. Включение c придает универсальному LC-алгоритму несколько лучшие статистические свойства по сравнению с алгоритмом Лемера. Демонстрационная реализация LC-алгоритма показана на рис. 4. Код основан на стандарте POSIX (Portable Operating System Interface).

Рис. 4. Реализация линейного конгруэнтного алгоритма

LC-алгоритм использует несколько битовых операций. Здесь идея в том, чтобы в базовых математических типах работать не с целым типом (32 бита), а с длинным целым (64 бита). По окончании 32 из этих битов (с 16-го по 47-й включительно) извлекаются и преобразуются в целое число. Этот подход дает более качественные результаты, чем при использовании просто 32 младших или старших битов, но за счет некоторого усложнения кодирования.

В демонстрации генератор случайных чисел LC вызывается так:

Заметьте, что в отличие от генераторов Лемера и Вичмана-Хилла генератор LC может принимать начальное значение 0. Конструктор в демонстрации LC копирует значение входного параметра seed непосредственно в член класса — поле seed. Многие распространенные реализации LC выполняют предварительные манипуляции над входным начальным значением, чтобы избежать генерации хорошо известных серий начальных значений.

Алгоритм Фибоначчи с запаздываниями

Этот алгоритм, выраженный уравнением, выглядит так:

Если на словах, то новое случайное число является тем, которое было сгенерировано 7 раз назад, плюс случайное число, сгенерированное 10 раз назад, и деленное по модулю на большое значение m. Значения (7, 10) можно изменять, как я вскоре поясню.

Допустим, что в некий момент времени последовательность сгенерированных чисел следующая:

где 561 — самое последнее из сгенерированных значений. Если m = 100, то следующим случайным числом будет:

Заметьте, что в любой момент вам всегда нужны 10 самых последних сгенерированных значений. Поэтому ключевая задача в алгоритме Фибоначчи с запаздываниями состоит в генерации начальных значений, необходимых для запуска процесса. Демонстрационная реализация алгоритма Фибоначчи с запаздываниями приведена на рис. 5.

Рис. 5. Реализация алгоритма Фибоначчи с запаздываниями

Демонстрационный код использует предыдущие случайные числа X(i–7) и X(i–10) для генерации следующего случайного числа. В научно-исследовательской литературе по этой тематике значения (7, 10) обычно обозначаются (j, k). Существуют другие пары (j, k), которые можно применять для алгоритма Фибоначчи с запаздываниями. Несколько значений, рекомендованных в хорошо известной книге «Art of Computer Programming» (Addison-Wesley, 1968), — (24,55), (38,89), (37,100), (30,127), (83,258), (107,378).

Чтобы инициализировать (j, k) в RNG Фибоначчи с запаздываниями, вы должны предварительно заполнить список значениями k. Это можно сделать несколькими способами. Однако наименьшее из начальных значений k обязательно должно быть нечетным. В демонстрации применяется грубый метод копирования значения параметра seed для всех начальных значений k с последующим удалением первой 1000 сгенерированных значений. Если значение параметра seed четное, тогда первое из значений k выставляется равным 11 (произвольному нечетному числу).

Чтобы предотвратить арифметическое переполнение, метод Next использует тип long для вычислений и математическое свойство: (a + b) mod n = [(a mod n) + (b mod n)] mod n.

Заключение

Позвольте мне подчеркнуть, что все четыре RNG, представленные в этой статье, предназначены только для некритичных случаев применения. С учетом этого я прогнал все RNG через набор хорошо известных базовых тестов на степень случайности, и они прошли эти тесты. Но даже при этом коварство RNG всем хорошо известно, и время от времени даже в стандартных RNG обнаруживаются дефекты, иногда лишь спустя годы их использования. Например, в 1960-х годах IBM распространяла реализацию линейного конгруэнтного алгоритма под названием RANDU, которая, как оказалось, обладала невероятно плохими качествами. А в Microsoft Excel 2008 была выявлена ужасно проблемная реализация алгоритма Вичмана-Хилла.

Нынешний фаворит в генерации случайных чисел — алгоритм Фортуна (Fortuna) (названный в честь римской богини удачи). Алгоритм Фортуна был опубликован в 2003 году и основан на математической энтропии плюс сложных шифровальных методах, таких как AES (Advanced Encryption System).

Джеймс Маккафри (Dr. James McCaffrey) — работает на Microsoft Research в Редмонде (штат Вашингтон). Принимал участие в создании нескольких продуктов Microsoft, в том числе Internet Explorer и Bing. С ним можно связаться по адресу jammc@microsoft.com.

Выражаю благодарность за рецензирование статьи экспертам Microsoft Крису Ли (Chris Lee) и Кирку Олинику (Kirk Olynyk).

Источник

Генерация случайных чисел на микроконтроллерах

Про генераторы случайных чисел написано очень много, но почти всегда, когда дело доходит до реализации, подразумевается (или явно говорится), что речь идет об x86/x64 и других «взрослых» архитектурах. В то же время, форумы, посвященные разработке устройств на микроконтроллерах, пестрят вопросами «как мне сгенерировать случайное число на %controllername%?». Причем диапазон ответов простирается от «смотри гугл/википедию» до «используй стандартную функцию». Далеко не всегда эта «стандартная функция» есть и устраивает разработчика по всем параметрам, чаще наоборот: то числа получаются далеки от случайных, то скорость работы слишком мала, а то полученный код вообще не помещается в свободную память.
Попробуем разобраться, какие бывают алгоритмы генерации случайных чисел, как выбрать подходящий, а главное, в чем особенности реализации этих алгоритмов на контроллерах.

Оценка «случайности»

Применения для ГСЧ могут найтись самые разные, от игрушек до серьезной криптографии. Соответственно, и требования, предъявляемые к генератору, тоже сильно варьируются. Для оценки качества (уровня «случайности») генератора существуют специальные тесты. Вот самые основные из них:

• Частотный тест. Состоит в подсчете количества нулей и единиц в последовательности битов. Единиц и нулей должно быть примерно поровну.
• Тест на последовательность одинаковых битов. Ищутся ряды одинаковых битов, вида 000. 0 или 111. 1. Распределение частот, с которыми встречаются ряды, в зависимости от их длины, должно соответствовать такому распределению для истинно случайного сигнала.
• Спектральный тест. К исходной последовательности применяется дискретное преобразование Фурье. Полученный спектр не должен иметь значительных пиков, которые говорили бы о наличии периодических свойств последовательности.
• Автокорреляционный тест. Подсчитывается значение корреляции между копиями последовательности, сдвинутыми друг относительно друга. Тест позволяет найти повторяющиеся участки в последовательности.

Существуют специальные наборы, включающие в себя десятки подобных тестов:
NIST — использовался в конкурсе AES для оценки алгоритмов шифрования.
DIEHARD — один из наиболее строгих существующих наборов.

Алгоритмы ГПСЧ

Любая последовательность, сгенерированная по жестко заданному алгоритму, не может считаться истинно случайной, поэтому, ведя речь об алгоритмических генераторах, употребляют термин псевдослучайная последовательность. Любой генератор псевдослучайных чисел (ГПСЧ) рано или поздно зацикливается, другое дело в том, что это «поздно» может наступить через несколько миллисекунд, а может через несколько лет. Длина цикла зависит от размера внутреннего состояния генератора N (фактически, это объем памяти, нужный генератору), и составляет от 2 (N/2) до 2 N бит.
Алгоритмов ГПСЧ придумано огромное множество, но далеко не все они удобны для реализации на микроконтроллерах. Мы сильно ограничены в быстродействии и доступном объеме памяти, многие контроллеры не поддерживают вещественную арифметику и даже команды умножения. Помня о подобных ограничениях, рассмотрим некоторые известные алгоритмы.

Линейный конгруэнтный метод

Очередной член последовательности рассчитывается по формуле
X_i+1 = (aX_i + c) mod m
Число m определяет максимальный период последовательности, целые числа a и c — «магические» коэффициенты. Число m разумно выбирать равным степени двойки, в таком случае опреация приведения по модулю сводится к отбрасыванию старших битов. Для того, чтобы получить максимальный период, нужно соблюдать следующие условия:
— c и m должны быть взаимно простыми,
— a-1 должно быть кратно p для всех простых делителей p числа m,
— если m кратно 4 (а в нашем случае оно будет кратно), то и a-1 должно быть кратно 4.
Есть еще одна тонкость: в качестве результата следует брать только старшие биты переменной состояния X, так как для младших бит статистические параметры случайности значительно хуже. Линейный конгруэнтный алгоритм обычно реализован в качестве стандартного rand() во многих библиотеках.

Плюсы:

• максимально возможный период для заданного размера переменной состояния;
• достаточно быстрый;
• часто уже реализован в библиотеке компилятора.

Минусы:

• требуется операция умножения;
• не все биты одинаково случайны.

Резюме: быстрый и простой алгоритм для не очень ответственных применений.

Метод Фибоначчи с запаздываниями

В этом алгоритме используется соотношение
X_i = X_i-a — X_i-b,
где переменная состояния X — беззнаковое целое. Величины запаздываний a и b берутся не какие угодно, а строго определенные, для достижения максимального качества рекомендуются пары (17,5), (55,24) или (97,33). Чем больше запаздывания, тем больше период и лучше спектральные свойства последовательности. С другой стороны, для работы генератора требуется хранить max предыдущих чисел, что не всегда приемлемо. Также для запуска генератора нужно max чисел, которые обычно получают при помощи более простого ГПСЧ.

Плюсы:

• не требует операций умножения;
• все биты случайного числа равнозначны по статистическим свойствам.

Минусы:

• требует большого объема памяти;
• требует большого массива чисел для запуска.

Резюме: очень качественный, но ресурсоемкий алгоритм.

Регистр сдвига с линейной обратной связью

Переменная состояния хранится в регистре длины N. Генерация следующего состояния включает два шага:

1. Подсчитывается значение бита C = X_i1 xor X_i2 xor… X_ik, где i1, i2… ik — номера битов регистра, называемые отводами.
2. Регистр сдвигается на 1 бит вправо, крайний левый бит принимает значение С.

Выходом генератора является крайний правый (или крайний левый, или любой другой) бит регистра, то есть псевдослучайная последовательность генерируется по одному биту за итерацию. При правильно выбранных номерах отводов период генератора составит 2 N — 1. «Минус один», так как существует запрещенное нулевое состояние регистра. Номера отводов для N от 3 до 168 можно посмотреть в этом документе.
Кроме описанной выше конфигурации, которая, кстати, называется конфигурацией Фибоначчи (не путать с одноименным методом ГПСЧ!), существует т.н. конфигурация Галуа.

Вместо того, чтобы использовать для генерации нового крайнего левого бита сумму битов отводной последовательности, выполняется XOR каждого бита отводной последовательности с крайним правым битом, затем выполняется циклический сдвиг всего регистра вправо. Эта схема сложнее для понимания, но проще в реализации, так как все опрерации XOR можно выполнить одновременно. По длине периода и качеству псевдослучайных чисел схемы Фибоначчи и Галуа эквивалентны.

Плюсы:

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

Минусы:

• нужно проверять начальное значение на неравенство нулю.

Резюме: очень быстрый и довольно качественный алгоритм.

Криптостойкие алгоритмы

Для применения в криптографии к ГПСЧ предъявляется еще одно существенное требование: необратимость. Все перечисленные выше алгоритмы этим свойством не обладают: зная несколько выходных значений ГПСЧ, можно, решив несложную систему уравнений, найти параметры алгоритма (те самые «магические» константы a, b, с и т.д). А зная параметры, можно воспроизвести всю псевдослучайную последовательность.
В качестве криптографически стойкого алгоритма ГПСЧ можно использовать любой достаточно сильный блочный шифр. Выбрав секретный ключ, можно получать блоки псевдослучайных чисел, применяя алгоритм к последовательным натуральным числам. Для N-битного блочного шифра период будет не больше 2 N . Безопасность такой схемы полностью зависит от секретности ключа.
Все современные криптографические алгоритмы проходят проверку на использование в качестве ГПСЧ, то есть, используя сертифицированный алгоритм, не нужно специально заботиться о статистических и спектральных свойствах выходного потока. Переживать нужно только о вычислительной «прожорливости» криптоалгоритмов. Если требуется выполнять большое количество операций шифрования, имеет смысл выбрать контроллер с аппаратными криптографическими блоками. Часто в таких контроллерах есть и весьма неплохой криптостойкий аппаратный ГПСЧ.

Источники энтропии

Как уже было сказано, используя только детерминированные алгоритмы, невозможно сгенерировать истинно случайное число. Поэтому обычно применяется связка ГПСЧ + внешний источник энтропии. Источник энтропии используется для задания начального значения для ГПСЧ, а задача последнего сводится к обеспечению спектральной и статистической чистоты последовательности. Что же можно использовать в качестве источника энтропии? Да практически что угодно.

Активность пользователя

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

Аналого-цифровой преобразователь

Во многих контроллерах есть встроенные АЦП. И во многих контроллерах они весьма посредственного качества, сделанные просто «чтобы было». Младшие биты результата АЦП почти всегда содержат значительный шум, даже если измеряется постоянное напряжение. Это можно использовать: подключите вход АЦП к напряжению питания через делитель, проведите несколько десятков измерений, возьмите младшие биты — вот вам отличное случайное число. Если АЦП содержит встроенный предусилитель, включите его, он тоже шумит.

Асинхронные генераторы

Можно использовать разницу периодов двух несинхронизированных тактовых генераторов. Большинство контроллеров содержат, например, сторожевой таймер. Для повышения надежности он тактируется от отдельного генератора, никак не связанного с основным тактовым сигналом. Достаточно подсчитать число тактов основного тактового сигнала за один период сторожевого таймера. Если подобрать периоды так, чтобы счетчик за время измерения многократно переполнился, можно получить достаточно случайное число. Недостаток этого метода — он требует много времени, до нескольких секунд.

Часы реального времени

Если в схеме есть часы реального времени, можно использовать их текущие показания для инициализации ГПСЧ. Например, преобразовав текущие дату/время в формат Unix time, мы получим сразу 32 бита, которые никогда больше не повторятся, если только не снимать показания чаще одного раза в секунду. Использование реального времени дает уникальность значений, но не дает никакой непредсказуемости, поэтому лучше комбинировать данный способ с другими.

RC-цепь

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

Выводим на этот порт сигнал «0» — конденсатор разряжается. Переключаем порт в режим входа — конденсатор начинает заряжаться. Когда напряжение на нем достигнет порога, вход переключится из состояния «0» в «1». Время заряда сильно зависит от многих факторов: напряжаения питания, дрейфа параметров RC-цепи, нестабильности порога, температуры, утечек, помех. Измеряя его с достаточной точностью и беря младшие биты, можно получить хорошую случайность.

Аппаратный генератор шума

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

Для того, чтобы порог срабатывания компаратора не влиял на статистические свойства полученного сигнала, применяют два генератора шума, работающие на один компаратор:

Заключение

Напоследок расскажу одну историю из жизни. Началась она с очередного заданного на форуме вопроса «как мне сгенерировать случайное число на контроллере?». Автор вопроса пояснил, что делает в качестве курсового проекта устройство, эмулирующее бросание игральной кости. После нескольких безуспешных попыток разобраться в алгоритмах, топикстартер поделился своим решением: он просто бросил 1000 раз настоящий кубик и забил полученными числами всю свободную память контроллера. Генератор с блеском прошел все тесты на «случайность», учитывая то, что за время демонстрации израсходовал меньше трети своего «запаса».
Следовательно, такое решение тоже имеет право на жизнь, особенно если предъявляются очень строгие требования к случайности чисел, но они требуются не слишком часто. Учитывая стремительно падающие цены на память, может быть разумным снабдить устройство флешкой с «запасом хаоса», которого хватит на все время жизни устройства.
Благодарю за внимание!

UPD1: Как было справедливо отмечено в комментариях, если предполагается атака на ГСЧ, и у злоумышленника будет аппаратный доступ к устройству, применять внешние источники энтропии нужно с большой осторожностью, так как не составляет большой сложности подменить сигнал от внешнего источника. Следует использовать внутренние источники, можно в дополнение к внешним.
Также хорошая идея — накапливать энтропию все свободное время, а использовать ее тогда, когда требуется сгенерировать очередное случайное число. Обычно в таких случаях используется т.н. Entropy pool — массив, над которым периодически выполняется одна из функций ГПСЧ, и куда постоянно подмешиваются данные из источников энтропии.

UPD2: Во многих случаях полезно содержимое Entropy pool (извините, не знаю нормального русского перевода) сохранять в EEPROM для того, чтобы после выключения-включения устройства не накапливать его заново. Это отностится, прежде всего, к получению энтропии методом асинхронных генераторов: при достаточно стабильных условиях после каждого включения может генерироваться одна и та же последовательность.
Если ожидается атака, примите меры против подмены содержимого EEPROM. Если позволяет контроллер, заблокируйте чтение/стирание/запись при помощи lock-битов, при включении контролируйте целостность EEPROM, хотя бы с помощью простейших контрольных сумм.

Источник