

def      a      (			A__	:   int      ,   A__	:   bool = False     )    ->      bool:





      """simple docstring"""



      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
      _lowercase	       =[
          2047,
          1373653,
          25326001,
          3215031751,
          2152302898747,
          3474749660383,
          341550071728321,
          1,
          3825123056546413051,
          1,
          1,
          318665857834031151167461,
          3317044064679887385961981,
      ]

      _lowercase	       =[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
      for idx, _p in enumerate(A__      ,   1     ):
            if n < _p:
                  # then we have our last prime to check
                  _lowercase	       =primes[:idx]
                  break
      _lowercase       ,       _lowercase	       =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:
            _lowercase	       =False
            for r in range(A__     ):
                  _lowercase	       =pow(A__      ,   d * 2**r      ,   A__     )
                  # see article for analysis explanation for m
                  if (r == 0 and m == 1) or ((m + 1) % n == 0):
                        _lowercase	       =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      (			)    ->      None:





      """simple docstring"""



      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()










from typing import TYPE_CHECKING

from ...utils import OptionalDependencyNotAvailable, _LazyModule, is_tf_available, is_torch_available


UpperCAmelCase__				   =		{
    "configuration_groupvit": [
        "GROUPVIT_PRETRAINED_CONFIG_ARCHIVE_MAP",
        "GroupViTConfig",
        "GroupViTOnnxConfig",
        "GroupViTTextConfig",
        "GroupViTVisionConfig",
    ],
}

try:
     if not is_torch_available():
          raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
     pass
else:
     UpperCAmelCase__				   =		[
         "GROUPVIT_PRETRAINED_MODEL_ARCHIVE_LIST",
         "GroupViTModel",
         "GroupViTPreTrainedModel",
         "GroupViTTextModel",
         "GroupViTVisionModel",
     ]

try:
     if not is_tf_available():
          raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
     pass
else:
     UpperCAmelCase__				   =		[
         "TF_GROUPVIT_PRETRAINED_MODEL_ARCHIVE_LIST",
         "TFGroupViTModel",
         "TFGroupViTPreTrainedModel",
         "TFGroupViTTextModel",
         "TFGroupViTVisionModel",
     ]

if TYPE_CHECKING:
     from .configuration_groupvit import (
         GROUPVIT_PRETRAINED_CONFIG_ARCHIVE_MAP,
         GroupViTConfig,
         GroupViTOnnxConfig,
         GroupViTTextConfig,
         GroupViTVisionConfig,
     )

     try:
          if not is_torch_available():
               raise OptionalDependencyNotAvailable()
     except OptionalDependencyNotAvailable:
          pass
     else:
          from .modeling_groupvit import (
              GROUPVIT_PRETRAINED_MODEL_ARCHIVE_LIST,
              GroupViTModel,
              GroupViTPreTrainedModel,
              GroupViTTextModel,
              GroupViTVisionModel,
          )

     try:
          if not is_tf_available():
               raise OptionalDependencyNotAvailable()
     except OptionalDependencyNotAvailable:
          pass
     else:
          from .modeling_tf_groupvit import (
              TF_GROUPVIT_PRETRAINED_MODEL_ARCHIVE_LIST,
              TFGroupViTModel,
              TFGroupViTPreTrainedModel,
              TFGroupViTTextModel,
              TFGroupViTVisionModel,
          )

else:
     import sys

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


