



"""simple docstring"""





def        a__     (				lowerCAmelCase__     ,      lowerCAmelCase__ = False				):
      if n == 2:
            return True
      if not n % 2 or n < 2:
            return False
      if n > 5 and n % 10 not in (1, 3, 7, 9):  # can quickly check last digit
            return False
      if n > 3317044064679887385961981 and not allow_probable:
            raise ValueError(
                "Warning: upper bound of deterministic test is exceeded. "
                "Pass allow_probable=True to allow probabilistic test. "
                "A return value of True indicates a probable prime."				)
      # array bounds provided by analysis
      UpperCAmelCase_      			=							[
          2047,
          1373653,
          25326001,
          3215031751,
          2152302898747,
          3474749660383,
          341550071728321,
          1,
          3825123056546413051,
          1,
          1,
          318665857834031151167461,
          3317044064679887385961981,
      ]

      UpperCAmelCase_      			=							[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
      for idx, _p in enumerate(__snake_case     ,      1				):
            if n < _p:
                  # then we have our last prime to check
                  UpperCAmelCase_      			=							primes[:idx]
                  break
      UpperCAmelCase_			,   UpperCAmelCase_      			=							n - 1, 0
      # break up n -1 into a power of 2 (s) and
      # remaining odd component
      # essentially, solve for d * 2 ** s == n - 1
      while d % 2 == 0:
            d //= 2
            s += 1
      for prime in plist:
            UpperCAmelCase_      			=							False
            for r in range(__snake_case				):
                  UpperCAmelCase_      			=							pow(__snake_case     ,      d * 2**r     ,      __snake_case				)
                  # see article for analysis explanation for m
                  if (r == 0 and m == 1) or ((m + 1) % n == 0):
                        UpperCAmelCase_      			=							True
                        # this loop will not determine compositeness
                        break
            if pr:
                  continue
            # if pr is False, then the above loop never evaluated to true,
            # and the n MUST be composite
            return False
      return True





def        a__     (				):
      assert not miller_rabin(561				)
      assert miller_rabin(563				)
      # 2047

      assert not miller_rabin(838201				)
      assert miller_rabin(838207				)
      # 1_373_653

      assert not miller_rabin(17316001				)
      assert miller_rabin(17316017				)
      # 25_326_001

      assert not miller_rabin(3078386641				)
      assert miller_rabin(3078386653				)
      # 3_215_031_751

      assert not miller_rabin(1713045574801				)
      assert miller_rabin(1713045574819				)
      # 2_152_302_898_747

      assert not miller_rabin(2779799728307				)
      assert miller_rabin(2779799728327				)
      # 3_474_749_660_383

      assert not miller_rabin(113850023909441				)
      assert miller_rabin(113850023909527				)
      # 341_550_071_728_321

      assert not miller_rabin(1275041018848804351				)
      assert miller_rabin(1275041018848804391				)
      # 3_825_123_056_546_413_051

      assert not miller_rabin(79666464458507787791867				)
      assert miller_rabin(79666464458507787791951				)
      # 318_665_857_834_031_151_167_461

      assert not miller_rabin(552840677446647897660333				)
      assert miller_rabin(552840677446647897660359				)
      # 3_317_044_064_679_887_385_961_981
      # upper limit for probabilistic test


if __name__ == "__main__":
  test_miller_rabin()









"""simple docstring"""





# Copyright 2023 The HuggingFace Team. All rights reserved.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
from typing import TYPE_CHECKING

from ...utils import OptionalDependencyNotAvailable, _LazyModule, is_torch_available


lowerCamelCase       	=						{
    """configuration_mgp_str""": ["""MGP_STR_PRETRAINED_CONFIG_ARCHIVE_MAP""", """MgpstrConfig"""],
    """processing_mgp_str""": ["""MgpstrProcessor"""],
    """tokenization_mgp_str""": ["""MgpstrTokenizer"""],
}

try:
  if not is_torch_available():
    raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
  pass
else:
  lowerCamelCase       	=						[
      """MGP_STR_PRETRAINED_MODEL_ARCHIVE_LIST""",
      """MgpstrModel""",
      """MgpstrPreTrainedModel""",
      """MgpstrForSceneTextRecognition""",
  ]

if TYPE_CHECKING:
  from .configuration_mgp_str import MGP_STR_PRETRAINED_CONFIG_ARCHIVE_MAP, MgpstrConfig
  from .processing_mgp_str import MgpstrProcessor
  from .tokenization_mgp_str import MgpstrTokenizer

  try:
    if not is_torch_available():
      raise OptionalDependencyNotAvailable()
  except OptionalDependencyNotAvailable:
    pass
  else:
    from .modeling_mgp_str import (
        MGP_STR_PRETRAINED_MODEL_ARCHIVE_LIST,
        MgpstrForSceneTextRecognition,
        MgpstrModel,
        MgpstrPreTrainedModel,
    )
else:
  import sys

  lowerCamelCase       	=						_LazyModule(__name__, globals()["""__file__"""], _import_structure, module_spec=__spec__)




